Fast modular multiplication using 2-power radix

Abstract

Details are given here of how to generalise Brickell's fast modular multiplication algorithm to when the number representations have a general 2-power radix. Correct action depends upon the satisfaction of a complicated inequality and speed upon the use of a redundant number system to enable parallel digit operations. The effect of varying the radix on the efficiency of hardware implementations is considered. Improved efficiency has repercussions in public key cryptography where the RSA encryption scheme may use this type of algorithm for its modular exponentiations. However, it is shown that there is no advantage in taking a very large radix, although a small increase above 2 is beneficial.

Keywords:

• Modular multiplication
• fast computer arithmetic
• digital arithmetic
• integer division
• parallel bit operations
• redundant number systems
• RSA algorithm
• cryptography