摘要
A new fast algorithm to compute modular exponentiation for very large integers is proposed in this paper, which is an improvement of the fast RSA algorithm based on Symmetry of Modular Multiplication(SMM). The SMM algorithm obtains the speed improvement by conditional substitution on every basic operation to decrease the absolute value of product and the operation numbers of modular reductions. The proposed algorithm can get faster operation speed by decreasing the numbers of basic operations. Compared to conventional binary representation, a speed improvement of approximately 47.5% would be expected using the proposed algorithm.
A new fast algorithm to compute modular exponentiation for very large integers is proposed in this paper, which is an improvement of the fast RSA algorithm based on Symmetry of Modular Multiplication(SMM). The SMM algorithm obtains the speed improvement by conditional substitution on every basic operation to decrease the absolute value of product and the operation numbers of modular reductions. The proposed algorithm can get faster operation speed by decreasing the numbers of basic operations. Compared to conventional binary representation, a speed improvement of approximately 47.5% would be expected using the proposed algorithm.
