Fast exponentiation by folding the signed-digit exponent in half

Abstract

For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation (M ^E mod N). The M, E and N are either as large as the 1024-bit integers or even larger, it is not a very good idea to directly compute M ^E mod N. Recently, there are many techniques have been invented to solve the time-consuming computations of such time-consuming modular exponentiation. Among these useful algorithms, the “binary (square-and-multiply) algorithm” reduces the amount of modulo multiplications. As the “signed-digit representation algorithm” has the property of the nonzero digit occurrence probability equals to 1/3, taking this advantage, this method can more effectively decrease the amount of modular multiplications. Moreover, by using the technique of recording the common parts in the folded substrings, the “folding-exponent algorithm” can improve the efficiency of the binary algorithm, thus can further decrease the computational complexity of modular exponentiation. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algorithm, signed-digit representation, and the folding-exponent technique. By using the parallel processing technique, in our proposed method, the modular multiplications and modular squaring can be executed in parallel, and thus lower down the computational complexity to k + 3 multiplications. As modular squaring operation over GF(2 ⁿ ) is carried out by a simple cyclic right shift operation, the computational complexity of our proposed method can be further reduced to 29k/36 + 3 multiplications.

Keywords:

• Modular exponentiation
• Computer arithmetic
• Public-key cryptography
• Signed-digit numbers
• Galois fields