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

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

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

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

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