Parallel modular exponentiation using signed-digit-folding technique

Fast modular exponentiation algorithms are often considered of practical significance in RSA cryptosystem. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algorithm, signed-digit representation, and the folding-exponent technique. As the "signed-digit recoding algorithm" has less occurrence probability of the nonzero digit than binary number representation. Taking this advantage, we can effectively decrease the amount of modular multiplications. 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. As the modular squaring operation in GF(2ⁿ) finite field can be done by a simple shift operation when a normal basis is used, and the modular multiplications and modular squaring operations in our proposed signed-digit recoding scheme can be executed in parallel, by using our proposed generalized r-radix signed-digit folding algorithm, we can decrease the computational complexity to 2^n-1{(4r+3/4(r+1)²)×k/2 ⁿ}+2ⁿ+(k-k/2ⁿ)+(2ⁿ-1) multiplications where k denotes the digit-length of the exponent and n denotes the folding time of the exponent, respectively. Furthermore, if we have the folding time n=1 to minimize the total multiplication complexity, we can obtain the optimal overall computational complexity as k/2+k/2[4r+3/4(r+1) ²]+3 multiplications in r-radix signed-digit recoding system.