An efficient Montgomery exponentiation algorithm for public-key cryptosystems

The well-know binary method is a generally acceptable method for modular exponentiation in public-key cryptosystems. In this paper, we propose a new binary exponentiation algorithm, which is based on common-multiplicand method, Montgomery modular reduction algorithm, signed-digit recoding technique, and binary exponentiation algorithm. The common-multiplicand technique is developed to solve the problem common-multiplicand multiplications, i.e., the same common part in two modular multiplications can be computed once rather twice. The "signed-digit recoding" has less occurrence probability of the nonzero digit than binary representation. Due to this advantage, we can efficiently lower down the amount of modular multiplications and we can therefore decrease the computational complexity of modular exponentiation. By using the proposed algorithm, the total number of multiplications can be reduced by about 66.7% as compared with the original Montgomery modular reduction algorithm.