RSA密码系统有效实现算法

Efficient Algorithms for RSA Cryptosystem Implementation

大整数模幂乘运算一直是制约RSA广泛应用的瓶颈,在对传统算法剖析的基础上,提出了一种新的快速模乘算法,借鉴生成Wallace tree的思想,结合查找表和并行乘法运算进行RSA模幂运算。理论分析和试验证明新算法时间复杂度降低到O(logn)。

Modular exponentiation of large integers is the choke point for RSA. After analyzing traditionalalgorithms, a new fast modular exponentiation algorithm was presented. Wallace tree, lookup table and parallel multiplication were used in the algorithm. With theoretical analyzing and practical application, it was shown that the time complexity of the new algorithm was reduced to O（logn）.