摘要：Fast modular exponentiation algorithms are often considered of practical signifi-cance in RSA cryptosystem. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algo-rithm, 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 com-mon 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(2n) finite field can be done by a simple shift operation when a normal basis is used, and the modular multiplications and modu-lar squaring operations in our proposed signed-digit recoding scheme can be exe-cuted in parallel, by using our proposed generalized r-radix signed-digit folding algorithm, we can decrease the computational complexity to 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 multiplications in r-radix signed-digit recoding system
