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

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

Implementations of the Improved AKS Primality Testing Algorithm

The AKS algorithm successfully solved the noted problem of deterministic primality testing in polynomial time,but it was not yet suitable for the real application,thus it was improved in series.In order to further analyze the practical efficiency of currently improved versions of the AKS algorithm,one of them(called the second AKS-Bernstein algorithm),which was proposed by Bernstein,was implemented by using Delphi-Pascal program on PC Pentium I V/1.8 G,and its running efficiency were compared with that of other versions.For data that formerly needed tens or thousands of hours to complete the primality test with previous versions,only several seconds were required when running with the second AKS-Bernstein algorithm.Thus,the conclusion that the second AKS-Bernstein algorithm is better than other improved versions was got.In addition,some defects of the second AKS-Bernstein algorithm were analyzed,and the suggestion that the second AKS-Bernstein algorithm remains to be improved was made.