http://www.alihk.net/~md/fun/stories/prime/prime.htm 關鍵字:烏蘭現象 賽爾伯格不等式 http://www.csie.nctu.edu.tw/~rjchen/BigPrime.files/show.htm 首先，由質數定理我們知道質數的分佈密度：小於或等於n的質數個數約等於n / loge n， 換句話說，當我們任意挑選一個數n，且這個數n是質數的機率約等於1 / loge n； 舉例來說，如果任意挑選一個100位數的整數，且挑到的整數又剛好是質數的機率約 為1 / loge 10100 ? 1/230，也就是平均每230次應該會有一個質數。 實際上這個數字可以透過一些篩選的技巧使得次數降低，例如判斷是否是 小質數2, 3, 5, 11的倍數來決定要不要成為候選質數，如此一來就可以將次數再降低。 如何檢驗質數 接著，我們說明如何做質數檢驗，這裡我們將檢驗通過的候選質數分為兩類： 一類是檢驗通過的候選質數有很大的機率真的是質數但不是絕對的，稱為可能質數 (probable prime)；另一類則是檢驗通過的質數真的就是質數， 稱為可證明質數(provable prime)。 以下我們就找第一類可能質數的檢驗法加以說明。這一類的檢驗法乍看之下似乎 沒有價值，然而由於其執行效率快，且可以透過重複多次的檢驗使得錯誤率迅速的 降到很低(如低於10-100)，因此在實際應用上，反而有較高的價值。 檢查一個整數是否是質數最直覺的方法就是試除法，把n用小於或等於√n的質數去試除， 如果都無法整除則n是質數，這個方法雖然看起來簡單，但執行起來卻十分費時， 一般來說當n是10位數時就已經很吃力了，更何況我們要的質數往往都是100位數以上。 1640年法國數學家費馬(Fermat)注意到質數的一個性質， 稱為費馬小定理(Fermat’s little theorem)： [費馬小定理] 若n是質數，則對所有與n互質的數a，an-1≡1 (mod n) 實際上當n不是質數的時候，有可能存在這樣一個a，使得an-1≡1 (mod n)， 這時候我們稱n為基於a的偽質數(base-a pseudoprime)，因此，根據定理的逆方向 設計的質數檢驗法稱為費馬檢驗(Fermat testing)。 -- 愛如果能從0開始 那就能回到過去了... 除非..一開始就是個錯誤... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.221.183.224