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 VLSI Algorithm for Modular Division Based on the Binary GCD Algorithm
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/05/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
modular arithmetic, modular division, GCD, hardware algorithm, redundant representation,
Full Text: PDF(379.3KB)
>>Buy this Article
An algorithm for modular division which is suitable for VLSI implementation is proposed. It is based on the plus-minus algorithm which is a modification of the binary method for calculating the greatest common divisor (GCD). The plus-minus algorithm for calculating GCD is extended for performing modular division. A modular division is carried out through iteration of simple operations, such as shifts and addition/subtractions. A redundant binary representation is employed so that addition/subtractions are performed without carry propagation. A modular divider based on the algorithm has a linear array structure with a bit-slice feature and carries out an n-bit modular division in O(n) clock cycles, where the length of clock cycle is constant independent of n.