一种新的快速RSA算法  

A New Fast RSA Algorithm

作　　者：许万福[1] 侯惠芳[1] 

机构地区：[1]河南工业大学信息科学与工程学院

出　　处：《计算机与数字工程》2009年第5期45-49,共5页Computer & Digital Engineering

基　　金：河南工业大学校基金项目(编号:08XJC010)资助

摘　　要：素性检测和模乘运算一直是制约RSA广泛应用的瓶颈,在对传统算法剖析的基础上,提出一种新的快速RSA算法。改进Miller-Rabin素性检测算法,借鉴生成Wallacetree的思想,结合映射表和并行乘法运算改进模乘运算。理论分析和试验证明新的Miller-Rabin算法素性检测概率远远大于(1-1/2(1/4n)),时间复杂度降低到O(n),新的模乘算法时间复杂度降低到O(logn)。最后,结合RSA算法的安全性用Delphi实现该算法。Primality testing and modular multiplication of large integers are the choke point for RSA. After analyzing traditional algorithms, a new fast RSA algorithm was presented. Improved Miller-Rabin, Wallace tree, map-table and parallel multiplication were used in the algorithm. With theoretical analyzing and practical application, it was shown that the probability of the new primality testing was far greater than （1-1/2 （1/4＇））, the time complexity of the new primality testing and the new modular multiplication was reduced to O （n） and O （nlogn） respectively. Finally, along with the security of RSA, the algorithm was developed by Delphi.

关 键 词：Lehmann Solovay-Strassen Eratosthenes Miller-Rabin模乘 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]