Efficient Modular Exponentiation Using Common-Multiplicand Multiplication and Signed-Digit Recoding Techniques

In many computation problem, the modular exponentiation is a common operation for scrambling secret data and is used by several public-key cryptosystems, such as the RSA method. In this paper, an algorithm is proved, which combines binary exponentiation method, the CMM (common-multiplicand multiplication) method, and the SDR (signed-digit recoding) method for fast modular exponentiation. The proposed algorithm developed in this paper can be easily implemented in general signed-digit computing machine, and is therefore well suited for parallel implementation to fast evaluate modular exponentiation. The computational complexity of the proposed algorithm is 0.46m3-0.92m2-3.67m multiplications, which is less than 0.75m3+0.75m multiplications in Dusse-Kaliski algorithm, 0.625m3+m2 multiplications in Ha-Moon algorithm, where m is the bit-length of the exponent.