A VLSI Algorithm for Modular Division Based on the Binary GCD Algorithm

Naofumi TAKAGI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.5   pp.724-728
Publication Date: 1998/05/25
Online ISSN: 
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.