AKS素性测定算法的一个改进版本在PC上的实现
AKS 算法从理论上成功解决了在多项式时间内进行确定性素性测定的著名难题,但它并不实用,从而得到一系列的改进.为深入分析现有AKS改进算法的实际应用效率, 利用 Delphi-Pascal 语言在微机Pentium IV/1.8G上实现了 AKS 算法的一个 Bernstein 改进版本(简称 AKS-Bernstein第二算法),并分析比较了AKS算法现有几个版本的实际耗时.对于原先需要几十甚至几千个小时才能完成一次素性测定的数据, 利用AKS-Bernstein第二算法进行测试仅需几十秒,从而指出该算法比其他版本有很大改进.此外,通过分析 AKS-Bernstein第二算法仍然存在的一些不足,指出该算法在素性测定的实际运用上还有待进一步完善.
素性测定、AKS算法、Rabin-Miller测试、算法实现
41
O156.2(代数、数论、组合理论)
国家高技术研究发展计划863计划资助项目2006AA01Z419;国家自然科学基金资助项目90604023,60873191,60821001;北京市自然科学基金项目4072020;高等学校博士学科点专项科研基金资助项目20040013007
2017-01-18（万方平台首次上网日期，不代表论文的发表时间）
共6页
147-152
