For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Hardware Algorithm for Modular Division Based on the Extended Euclidean Algorithm
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/11/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Hardware and Design
Euclidean algorithm, hardware algorithm, modular arithmetic, modular division, redundant representation,
Full Text: PDF>>
A hardware algorithm for modular division is proposed. It is based on the extended Euclidean algorithm (EEA). The procedure for finding the multiplicative inverse in EEA is modified so that it calculates the quotient. Modular division is carried out through iteration of simple operations, such as shifts and additions. A redundant binary representation is employed so that additions are performed without carry propagation. An n-bit modular division is carried out in O(n) clock cycles. The length of each clock cycle is constant independent of n. A modular divider based on the algorithm has a bit-slice structure and is suitable for VLSI implementation.