TY - JOUR

T1 - Fast exponentiation by folding the signed-digit exponent in half

AU - Lou, Der Chyuan

AU - Wu, Chia Long

AU - Chen, Chin Yin

PY - 2003/10

Y1 - 2003/10

N2 - For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation (ME 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 ME 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(2n) 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.

AB - For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation (ME 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 ME 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(2n) 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.

KW - Computer arithmetic

KW - Galois fields

KW - Modular exponentiation

KW - Public-key cryptography

KW - Signed-digit numbers

UR - http://www.scopus.com/inward/record.url?scp=28244460753&partnerID=8YFLogxK

U2 - 10.1080/00207160310001624223

DO - 10.1080/00207160310001624223

M3 - 文章

AN - SCOPUS:28244460753

SN - 0020-7160

VL - 80

SP - 1251

EP - 1259

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 10

ER -