壹種適用於32位機器號的確定性素數確定方法
作者:
王浩(great_wh@tom.com)
本文投稿是為了發表個人研究成果，與大家分享。我的教育背景如下:
計算機應用/管理工程雙學士學位
天津大學
1995到1999在校學習。
日期:2006年_ _ _ _ _ _ _ _ _ _ _月-28日
摘要
壹種適用於32位機器號的確定性素數確定方法
作者:王浩
本文通過研究Miller-Rabin的非確定性素數判定方法如何轉化為確定性素數判定方法，發現了與之相關的偽素數的壹些性質，引入了偽素數的最小可確定基的概念，總結了壹些規律。通過這些規律，找到了壹種確定性的素數判定方法，特別適用於32位機器數。這種方法對於32位機器號最多只需要16log(n)次乘/除。該方法實現簡單，速度快，非常值得推廣。
如果文中總結的壹些規律能夠得到證明和推廣，就有可能徹底解決將Miller-Rabin不確定性素數判定方法轉化為確定性素數判定方法的問題，從而在壹定程度上推動素數判定的理論和實踐。
本文共分五章。細分如下:
第壹章:介紹了素數判定方法的現狀，列舉了壹些常用的素數判定方法及其適用範圍。
第2章:說明偽素數表的生成過程。
第三章:對偽素數表進行了分析，引入了偽素數的最小可決定基的概念，並總結了壹些規律。根據這些規律，找到了特別適用於32位機的確定性素數判定方法，並進行了多方面的優化，給出了時間復雜度分析。
第4章:算法的C++語言實現和說明。
第五章:算法的可推廣性分析和未來發展展望。
目錄
第壹章素數判定的現狀...1
第2章-偽素數表的生成...
第三章尋找2-偽素數的最小可判定基...3
第四章算法實現和解釋...5
第五章算法的可推廣性分析...8
參考...9
詞匯
素數判定法:判定自然數是否為素數的方法。
確定性素數判定法:素數判定法判定自然數為素數的壹個充要條件是該自然數確實是素數，這種判定法是確定性素數判定法。即這種判斷方法不存在誤判的可能。
32位機器號:在計算機上用32個二進制位表示的無符號整數。
64位機器號:在計算機上用64個二進制位表示的無符號整數。
第壹章是素數判定方法的現狀
目前確定確定性素數的方法有很多，如試錯法、Williams法、Edelman法、Rumeli法等。它們的應用範圍是不同的。Williams方法更適用於10 20和10 50之間的數字，Edelman和Rumeli方法適用於大於10 50的數字。對於32位機，因為都小於10 10，所以壹般都是通過試錯來判斷。
有人可能會問，“為什麽沒有提到馬寧德拉阿格拉法？”？不是說是目前最快的素數確定方法嗎？“其實，這是壹個很大的誤會。阿格拉瓦法雖然是log(n)的多項式級算法，但目前只具有理論意義，根本無法應用，因為其時間復雜度為O (log (n) 12)，而且這個多項式的次數太高。和最慢的試分比。試分的時間復雜度為O (n (1/2) * log (n) 2)。當n = 16時，log(n)12 = 1677 7265438。如果要使兩個速度相等，即log(n)12 = n(1/2)* log(n)2，則得到n = 10 43.1214。此時要進行的運算次數為log (n) 12 = 10 25.873(註:本文中log()函數默認以2為基數)，在主頻為3GHz的計算機上完成這樣的運算需要10 8.89707年。看來這輩子我們不壹樣了。
除了這些確定性的素數判定方法，還有基於概率的非確定性素數判定方法，最常用的方法是米勒-拉賓法。
對於32位機器號(四次運算都在常數時間內完成)，試除法的時間復雜度為O (n (1/2))，而米勒-拉賓法的時間復雜度僅為O(log(n))。所以後者要比前者快得多，但是由於米勒-拉賓方法的不確定性，我們在需要確定解的時候往往還是要靠慢試慢分。能否通過擴展米勒-拉賓方法找到壹種更快的確定性素數判定方法？結論是肯定的，本文就帶妳找到這樣的方法。
第2章-偽素數表的生成
既然要推廣米勒-拉賓方法，首先要知道為什麽米勒-拉賓方法是壹種不確定的素數判定方法。答案很簡單，因為偽素數的存在。因為米勒-拉賓法是用費馬大定理的逆命題來判斷的，而這個逆命題對於少數合數不成立，導致誤判。這些使費馬大定理的逆命題成立的合數是偽素數。為了研究偽素數，我們首先需要生成壹個偽素數表。原理很簡單，就是我們先用篩選法得到某個範圍內的所有素數，然後判斷這個範圍內的所有合數是否使以2為底的費馬大定理逆命題壹壹不成立，從而得到這個範圍內的壹個2-偽素數表。我的程序運行了100分鐘，得到了壹個32位機範圍內的2個偽素數的表，如下:
341
561
645
1105
1387
1729
1905
2047
2465
2701
...
...
...
4286813749
4288664869
4289470021
4289641621
4289884201
4289906089
4293088801
4293329041
4294868509
4294901761
(***10403，由於篇幅限制，省略了中間部分。)
第三章，求2-偽素數的最小可決定基。
對於2-偽素數表中的每個偽素數，找出能確定它們是合數的最小基。我稱這個基為最小可確定基。特別地，對於壹個絕對偽素數，它的最小素因子是它的最小可確定基。既然已經證明絕對偽素數至少有三個素因子，那麽最小素因子壹定不能大於n (1/3)。下面是我找到的最小可確定基的列表:
341 3
561 3
645 3
1105 5
1387 3
1729 7
1905 3
2047 3
2465 5
2701 5
...
...
...
4286813749 3
4288664869 3
4289470021 5
4289641621 3
4289884201 3
4289906089 3
4293088801 3
4293329041 3
4294868509 7
4294901761 3
通過統計這個列表，我發現了壹個規律，那就是所有的最小可確定基都不大於n (1/3)。從上面可以看出，對於絕對偽素數，這個結論顯然是成立的。至於非絕對偽素數，雖然直觀上應該比絕對偽素數判斷得更好，但我無法證明它的最小可確定基不大於N (1/3)。不過沒關系，這個問題還是留給數學家們作為猜想去解決吧。更重要的是，我通過實驗證明了這個結論在32位機範圍內是成立的。
我們有更好的方法來進壹步縮小最小可確定基的範圍嗎？是啊！我們可以在計算平方數的時候進行二次檢驗。以下是二次測試後重新計算的最小可確定基數列表:
341 2
561 2
645 2
1105 2
1387 2
1729 2
1905 2
2047 3
2465 2
2701 2
...
...
...
4286813749 2
4288664869 2
4289470021 2
4289641621 2
4289884201 2
4289906089 2
4293088801 2
4293329041 2
4294868509 2
4294901761 3
顯然，第二次測試是有效的。經過統計，我發現了壹個新的規律，就是第二次測試後，所有的最小可確定基都不大於N (1/6)，真的開了壹個正方形，哈哈！這個結論的數學證明還是留給數學家們作為猜測。我把這兩個猜想稱為費馬大定理可確定上界猜想。而且我已經完成了32位機範圍的證明。
通過上面總結的規律，我們已經可以設計出壹種O (n (1/6) * log (n))的確定性方法來確定32位機器的素數。但是這還不夠，我們還可以優化，因為最小可確定基列表重復後只剩下五個數(全是質數):{2，3，5，7，11}。天啊，是前五個質數，太好記了。
但在實現算法時，需要註意的是，這些結論都是基於2-偽素數表的，也就是說，2的判定步驟在任何情況下都是必不可少的，即使是在2 >: N (1/6)的情況下。
還有壹些優化可以用。經過實驗，當n & gt當= 7 6時，可以用{2，5，7，11}代替N (1/6)上界，也是100%正確。這樣判斷次數可以減少到4次以內，每次判斷只需要4log(n)次乘除運算(余數運算也視為除法)，所以總計算次數不會超過16log(n)。通過實驗，最大計算次數出現在n=4294967291時，為496次。
第四章是算法的實現和說明。
算法實現如下:(使用C++語言)
# include & ltiostream & gt
# include & ltmath.h & gt
使用命名空間std
//定義跨平臺的64位機器號類型。
#ifndef _WIN32
typedef無符號long long long _ t；
#否則
typedef unsigned _ _ int 64 long long _ t；
#endif
//利用費馬定理和二次檢測判斷壹個基數。
bool IsLikePrime(longlong_t n，longlong_t base)
{
longlong _ t power = n-1；
longlong_t結果= 1；
longlong_t x =結果；
longlong_t位= 0；
longlong _ t power 1 = power；
//計算二進制數字
while(power 1 & gt；0)
{
power 1 & gt；& gt= 1;
bits++；
}
//冪的二進制位從高階到低階處理。
while(bits & gt；0)
{
位-；
結果=(x * x)% n；
//二次檢測
if(result = = 1 & amp；& ampx！= 1。& ampx！= n-1)
{
返回false
}
if((power & amp；((longlong _ t)1 & lt；& lt位))！= 0)
{
結果=(結果*基數)% n；
}
x =結果；
}
//費馬小定理逆命題的判定
返回結果= = 1；
}
//前五個質數
const int primes[]={2，3，5，7，11 }；
//前5個素數的6次方，由後面的init對象初始化。
int primes _ six[sizeof(primes)/sizeof(primes[0])]；
//靜態初始化類
CInit級
{
公共:
CInit()
{
int num = sizeof(primes)/sizeof(primes[0])；
for(int I = 0；我& ltnumi++)
{
素數_六個[i] =素數[I]*素數[I]*素數[I]；
素數_六[i] *=素數_六[I]；
}
}
} init
//王浩素數判定函數
布爾判斷程序(longlong_t n)
{
如果(n & lt2)
返回false
如果(n == 2)
返回true
int num = sizeof(素數)/sizeof(int)；
bool bis large =(n & gt；= primes _ six[3])；
for(int I = 0；我& ltnumi++)
{
if (bIsLarge)
{
//當n > = 7 ^ 6時，不判斷上界，固定{2，5，7，11}進行判斷。
if(素數[i] == 3)
繼續；
}
其他
{
//當n
if(素數[i]！= 2 & amp& ampn & lt素數_六[i])
打破；
}
//做壹個子決定。
如果(！IsLikePrime(n，primes[i]))
返回false
}
//如果所有子判斷都通過，那麽n壹定是質數！
返回true
}
//主程序
int main()
{
longlong _ t n；
//確定每個標準輸入數的素數。
而(CIN & gt；& gtn)
{
if (JudgePrime(n))
{
//如果是質數，則輸出到標準輸出。
cout & lt& ltn & lt& ltendl
}
//如果是合數，則不輸出。
}
返回0；
}
節目中加入了足夠多的評論，應該不難理解。
需要註意的是，雖然我用了longlong_t進行輸入，但這是為了類型壹致性，有效輸入範圍仍然是0 ~ 2 32-1。
第五章:算法的可推廣性分析。
如果費馬大定理可以確定上界猜想可以證明，那麽算法可以推廣到n的任意數，時間復雜度為O (n (1/6) * log (n) 3)。這樣就可以完成從米勒-拉賓非確定性素數判定方法到確定性素數判定方法的轉化，這是對數論的補充，對米勒-拉賓素數判定方法在實際中的使用具有指導意義。
本文所做的研究只是向米勒-拉賓不確定素數判斷方法的確定性邁進了壹小步。相信在不久的將來，米勒-拉賓的不定素數判定方法的確定性會有更大的進展，對數論的理論和實踐都會產生深遠的影響。
參考
《計算機算法設計與分析》(第2版)，王曉東主編，電子工業出版社，2004年7月。