An efficient Montgomery exponentiation algorithm by using signed-digit-recoding and folding techniques

摘要

The motivation for designing fast modular exponentiation algorithms comes from their applications in computer science. In this paper, a new CSD-EF Montgomery binary exponentiation algorithm is proposed. It is based on the Montgomery algorithm using the canonical-signed-digit (CSD) technique and the exponent-folding (EF) binary exponentiation technique. By using the exponent-folding technique of computing the common parts in the folded substrings, the same common part in the folding substrings can be simply computed once. We can thus improve the efficiency of the binary exponentiation algorithm by decreasing the number of modular multiplications. Moreover, the “signed-digit representation” has less occurrence probability of the nonzero digit than binary number representation. Taking this advantage, we can further effectively decrease the amount of modular multiplications and we can therefore decrease the computational complexity of modular exponentiation. As compared with the Ha–Moon’s algorithm 1.261718m multiplications and the Lou-Chang’s algorithm 1.375m multiplications, the proposed CSD-EF Montgomery algorithm on average only takes 0.5m multiplications to evaluate modular exponentiation, where m is the bit-length of the exponent.