论文部分内容阅读
素性测定问题是计算数论的中心课题之一.2002年8月,印度计算机科学家Agrawal,Kayal和Saxena在他们的网站上公布了全球第一个多项式时间严格素性证明算法(AKS算法),这是国际数学界和计算机科学界的一个重大理论成就.但因多项式时间的方次较高,AKS算法还不实用而有待改进.Bernstein首先给出一个比较好的改进算法(简称AKS-Bernstein第一算法).朱文余在微机同禧3206c/850上用C语言实现了AKS算法及上述改进,前一算法对3640471进行测试约需2478:94小时,而后者对4295884871进行测试约需28:35小时,从而指出在实际运用中直接利用AKS算法进行素性测定几乎不可能,而AKS-Bernstein第一算法比AKS算法有一些改进,但仍不实用.几乎与此同时,Berrizbeitia提出对限定条件的一类整数进行素性测定的AKS算法改进版本(简称AKS-Berrizbeitia算法).后来,Bernstein又提出一个比AKS-Berrizbeitia算法更一般的基本上随机四次多项式时间素性证明的AKS算法改进版本(简称AKS-Bernstein第二算法). 本文首先描述用Delphi-Pascal语言在PC Pentium IV/1.8G上对AKS-Berriz-beitia算法的实现,据此对仅五位的整数进行测试约需两个小时,从而指出AKS-Berrizbeitia算法仍不实用.然后从实现的角度考虑AKS-Bernstein第二算法中唯一令人感兴趣的一种情形,对其进行具体实现.对于上述所有被测整数,此算法均只需几秒钟即可完成素性证明,甚至对于某些15位和41位的素数,该算法也分别可在3分钟和10小时之内完成测试.再结合对于上述算法运算量的比较,指出AKS-Bernstein第二算法的确比AKS算法先前三个版本有很大的改进.最后通过分析AKS-Bernstein第二算法及其实现存在的一些不足,并通过横向比较AKS-Bernstein第二算法和由几个Miller测试组合成的确定性素性测试的运行效率,得出在十几位整数范围内后者比前者快几千倍,从而指出AKS-Bernstein第二算法及其实现工作还有待进一步完善,同时指出关于由几个Miller测试组合成的确定性素性测试的研究有着非常重要的实际意义.