A VLSI ALGORITHM FOR MODULAR DIVISION BASED ON THE BINARY GCD ALGORITHM

An algorithm for modular division which is suitable for VLSI implement ation 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 extende d for performing modular division. A modular division is carried out t hrough iteration of simple operations, such as shifts and addition/sub tractions. A redundant binary representation is employed so that addit ion/subtractions are performed without carry propagation. A modular di vider based on the algorithm has a linear array structure with a bit-s lice feature and carries out an n-bit modular division in O(n) clock c ycles, where the length of clock cycle is constant independent of n.