AKS素性測定算法兩個改進版本在PC上的實現(xiàn).pdf

1、素性測定問題是計算數(shù)論的中心課題之一.2002年8月,印度計算機科學家Agrawal,Kayal和Saxena在他們的網(wǎng)站上公布了全球第一個多項式時間嚴格素性證明算法(AKS算法),這是國際數(shù)學界和計算機科學界的一個重大理論成就.但因多項式時間的方次較高,AKS算法還不實用而有待改進.Bernstein首先給出一個比較好的改進算法(簡稱AKS-Bernstein第一算法).朱文余在微機同禧3206c/850上用C語言實現(xiàn)了AKS算法及上

2、述改進,前一算法對3640471進行測試約需2478:94小時,而后者對4295884871進行測試約需28:35小時,從而指出在實際運用中直接利用AKS算法進行素性測定幾乎不可能,而AKS-Bernstein第一算法比AKS算法有一些改進,但仍不實用.幾乎與此同時,Berrizbeitia提出對限定條件的一類整數(shù)進行素性測定的AKS算法改進版本(簡稱AKS-Berrizbeitia算法).后來,Bernstein又提出一個比AKS-B

3、errizbeitia算法更一般的基本上隨機四次多項式時間素性證明的AKS算法改進版本(簡稱AKS-Bernstein第二算法).
　　本文首先描述用Delphi-Pascal語言在PC Pentium IV/1.8G上對AKS-Berriz-beitia算法的實現(xiàn),據(jù)此對僅五位的整數(shù)進行測試約需兩個小時,從而指出AKS-Berrizbeitia算法仍不實用.然后從實現(xiàn)的角度考慮AKS-Bernstein第二算法中唯一令人感興趣的

4、一種情形,對其進行具體實現(xiàn).對于上述所有被測整數(shù),此算法均只需幾秒鐘即可完成素性證明,甚至對于某些15位和41位的素數(shù),該算法也分別可在3分鐘和10小時之內(nèi)完成測試.再結(jié)合對于上述算法運算量的比較,指出AKS-Bernstein第二算法的確比AKS算法先前三個版本有很大的改進.最后通過分析AKS-Bernstein第二算法及其實現(xiàn)存在的一些不足,并通過橫向比較AKS-Bernstein第二算法和由幾個Miller測試組合成的確定性素性測