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

Implementations of the Improved AKS Primality Testing Algorithm

作　　者：金正平[1] 温巧燕[1] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室,北京100876

出　　处：《四川大学学报（工程科学版）》2009年第1期147-152,共6页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家高技术研究发展计划(863计划)资助项目(2006AA01Z419);国家自然科学基金资助项目(90604023;60873191;60821001);北京市自然科学基金项目(4072020);高等学校博士学科点专项科研基金资助项目(20040013007)

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

关 键 词：素性测定 AKS算法 Rabin-Miller测试 算法实现 

分 类 号：O156.1[理学—数学]