摘要
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...
出处
《四川大学学报（工程科学版）》
EI
CAS
CSCD
北大核心
2009年第1期147-152,共6页
Journal of Sichuan University (Engineering Science Edition)
基金
国家高技术研究发展计划(863计划)资助项目(2006AA01Z419)
国家自然科学基金资助项目(90604023
60873191
60821001)
北京市自然科学基金项目(4072020)
高等学校博士学科点专项科研基金资助项目(20040013007)
