摘要： Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时，Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin算法底层运算的优化，可以取得较以往实现更好的性能。

关键词: 素数, 算法, 时间复杂度, 误判概率, 密码学

Abstract: 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.

中图分类号: 

• TP309