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

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

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

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

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