第一章 素數判定法現狀
現在，確定性素數判定法已經有很多種，常用的有試除法、威廉斯方法、艾德利曼和魯梅利法。它們的適用范圍各不相同，威廉斯方法比較適合10^20到10^50之間的數，艾德利曼和魯梅利法適合大于10^50的數，對于32位機器數，由于都小于10^10，所以一般都用試除法來判定。
也許有人會問：“你為什么沒有提馬寧德拉.阿格拉瓦法呢？不是有人說它是目前最快的素數判定法嗎？” 其實這是一個很大的誤解，阿格拉瓦法雖然是log(n)的多項式級算法，但目前只有理論上的意義，根本無法實用，因為它的時間復雜度是O(log(n)^12)，這個多項式的次數太高了。就拿最慢的試除法跟它來比吧，試除法的時間復雜度為O(n^(1/2)*log(n)^2)，當n = 16時，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要讓兩者速度相當，即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位機器數范圍內的證明。
通過上面總結的規律，我們已經可以設計出一個對32位機器數進行素數判定的 O(n^(1/6)*log(n)) 的確定性方法。但是這還不夠，我們還可以優化，因為此時的最小可判定底數列表去重后只剩下了5個數（都是素數）：{2,3,5,7,11}。天哪，就是前5個素數，這也太容易記憶了吧。
不過在實現算法時，需要注意這些結論都是在2-偽素數表基礎上得來的，也就是說不管如何對2的判定步驟必不可少，即使當2>n^(1/6)時。
還有一些優化可以使用，經過實驗，當n>=7^6時，可以不進行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正確的。這樣就可以把判定次數降為4次以下，而每次判定只需要進行4log(n)次乘除法（把取余運算也看作除法），所以總的計算次數不會超過16log(n)。經過實驗，最大的計算次數在n=4294967291時出現，為496次。
自己寫了個隨機化素數判定算法：
1 #include <iostream>
2 #include <cmath>
3 #include <algorithm>
4
5 using namespace std;
6 typedef unsigned __int64 longlong_t;
7
8 bool _IsLikePrime(longlong_t n, longlong_t base)
9 {
10 longlong_t power = n-1;
11 longlong_t result = 1;
12 longlong_t x = result;
13 longlong_t bits = 0;
14 longlong_t power1 = power;
15 //統計二進制位數
16 while (power1 > 0)
17 {
18 power1 >>= 1;
19 bits++;
20 }
21 //從高位到低位依次處理power的二進制位
22 while(bits > 0)
23 {
24 bits--;
25 result = (x*x)%n;
26 //二次檢測
27 if(result==1&&x!=1&&x!=n-1)
28 return false;
29
30 if ((power&((longlong_t)1<<bits)) != 0)
31 result = (result*base)%n;
32
33 x = result;
34 }
35 //費爾馬小定理逆命題判定
36 return result == 1;
37 }
38 inline bool JudgePrime(int n,int s)
39 {
40 srand(20);
41 for(int i=0;i<s;i++){
42 int a=rand()%(n-1)+1;
43 if(!_IsLikePrime(n,a))
44 return false;
45 }
46 return true;
47 }
48 int main()
49 {
50 int n;
51 while(scanf("%d",&n)!=EOF){
52 int num=0;
53 int cnt=0;
54 for(int i=0;i<n;i++){
55 scanf("%d",&num);
56 if(JudgePrime(num,20))
57 cnt++;
58 }
59 printf("%d\n",cnt);
60 }
61 return 0;
62 }
s越大，穩定性越好，但效率會低點。原作者有更好的判定算法，對作者表示感謝。。
posted on 2008-01-26 09:37
小果子 閱讀(1203)
評論(0) 編輯 收藏 引用 所屬分類:
學習筆記