A sequential modular multiplication algorithm using residue signed-digit additions
Shugang Wei · 2011
This paper proposes a new algorithm of sequential modular multiplication based on residue signed-digit(SD) number arithmetic. By introducing a p-digit radix-two SD number system into the residue arithmetic, a modular addition is easily implemented by using one or two SD adders for a modulus m, where 2p- 1 ≤ m ≤ 2p+1- 1, and no carry propagations will arise during the additions. In order to reduce the hardware cost and the delay time of the SD adders, we present a new architecture using binary numbers for the intermediate sum and carry within the SD adder. A modular multiplication can be performed by repeating the proposed residue addition of residue partial products. We also give a new architecture with the proposed residue SD adders to realize a faster modular multiplication. The design result shows that a modular multiplier can be improved in computing time and area based on the presented method.