AKS素性测定算法的一个改进版本在PC上的实现

作者：金正平; 温巧燕

来源：四川大学学报(工程科学版), 2009, (01): 147-152.

DOI：10.15961/j.jsuese.2009.01.013

• 素性测定
• AKS算法
• Rabin-Miller测试
• 算法实现 primality testing
• AKS algorithm
• Rabin-Miller test
• implementation of an algorithm

AKS算法从理论上成功解决了在多项式时间内进行确定性素性测定的著名难题,但它并不实用,从而得到一系列的改进。为深入分析现有AKS改进算法的实际应用效率,利用Delphi-Pascal语言在微机Pentium IV/1.8G上实现了AKS算法的一个Bernstein改进版本(简称AKS-Bernstein第二算法),并分析比较了AKS算法现有几个版本的实际耗时。对于原先需要几十甚至几千个小时才能完成一次素性测定的数据,利用AKS-Bernstein第二算法进行测试仅需几十秒,从而指出该算法比其他版本有很大改进。此外,通过分析AKS-Bernstein第二算法仍然存在的一些不足,指出该算法在素性测...