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 2n-1 ≤ N < 2n 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 2n-1 ≤ N < 2n, 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.
|Number of pages||4|
|Publication status||Published - 1989 Dec 1|
|Event||International Symposium on VLSI Technology, Systems and Applications - Proceedings of Technical Papers - Taipei, Taiwan|
Duration: 1989 May 17 → 1989 May 19
|Other||International Symposium on VLSI Technology, Systems and Applications - Proceedings of Technical Papers|
|Period||89-05-17 → 89-05-19|
All Science Journal Classification (ASJC) codes