Fast modular multiplication based on complement representation and canonical recoding
Chia-Long Wu, Der‐Chyuan Lou, Te-Jen Chang · International Journal of Computer Mathematics · 2010
Modular multiplication is the fundamental operation in implementing circuits for cryptosystem, as the process of encrypting and decrypting a message requires modular exponentiation that can be decomposed into multiplications. In this paper, a proposed multiplication method utilizes the complement recoding method and canonical recoding technique. By performing the complement representation method and canonical recoding technique, the number of partial products can be further reduced. Based on these techniques, an algorithm with efficient multiplication method is proposed. For multiplication operation, in average case, the proposed algorithm can reduce the number of k-bit additions from 1/4k+(log (k)/k)+5/2 to 1/6k+(log (k)/k)+5/2, where k is the bit length of the multiplicand and multiplier. Besides, if we perform the proposed technique to compute common-multiplicand multiplication, the computational complexity can reduce the number of k-bit additions from 1/2k+2×(log (k)/k)+5 to 1/3k+2×(log (k)/k)+5. We can, therefore, efficiently speed up the overall computing performance of the multiplication operation.