A new architecture for fast modular multiplication

An algorithm for computing AB mod N is developed, where N can be any positive integer. Since a carry-save adder can be used to implement the algorithm, a VLSI (very-large-scale integration) multiplier with area O(n) for multiplying n-bit integers is very fast. It is shown that n-bit AB mod N operation with 2^n-1⩽N<2ⁿ requires n short-period cycles and at most six long-period cycles. The period of the short cycles is independent of the size of the multiplier, and the long period is equal to the n-bit full-adder propagation delay time. If N is not in the interval 2^n-1 ⩽N<2ⁿ, the VLSI circuit needs more than six long-period cycles. The parallel adder can be replaced by a carry-lookahead adder to improve the speed. The multiplier was designed, and no error was found in its logic simulation. The architecture of the multiplier has regular, modular and expansible features and is therefore suitable for VLSI implementation