Miller-Rabin算法研究与优化实现  

Research and Efficient Implementation of Miller-Rabin Algorithm

作　　者：秦晓东[1] 辛运帏[1] 卢桂章[1] 

机构地区：[1]南开大学机器人与信息自动化研究所,天津300071

出　　处：《计算机工程》2002年第10期55-57,共3页Computer Engineering

基　　金：国家重点科技项目(攻关)计划资助项目(2000-A31-01-05); 天津市(重点)自然科学基金资助项目(013800111)

摘　　要：Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时，Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin算法底层运算的优化，可以取得较以往实现更好的性能。Miller-Rabin algorithm is the main stream probabilistic primality test algorithm, and is very important in constructing cryptography security system. When lots of primality test algorithms have been compared and Miller-Rabin algorithm has been researched in detail ,it is proved that Miller-Rabin algorithm is the best choice to be used in constructing cryptography security system to perform primality test. The performance of Miller-Rabin can be improved by optimizing the low level operations.

关 键 词：Miller-Rabin算法 优化 素数 时间复杂度 误判概率 密码学 信息安全 计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP309[自动化与计算机技术—计算机科学与技术]