Computation of modular multiplicative inverses using residue signed-digit additions

摘要

This paper proposes a new algorithm of calculating modular multiplicative inverse numbers 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 implemented by using two SD adders for a modulus m, where 2p - 1 ≤ m ≤ 2p+1 - 1, and no carry propagations will arise during the additions. We give a new architecture with the residue SD adder to realize a faster modular multiplicative inverse computation. The design result shows that the proposed circuits using the SD arithmetic are faster than that based on the binary ones.