費馬質數判定法
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
費馬質數判定法是一種質數判定法則,利用隨機化算法判斷一個數是合數還是可能是質數。
概念
根據費馬小定理:如果p是質數,,那麼
- 。
如果我們想知道n是否是質數,我們在中間選取a,看看上面等式是否成立。如果對於數值a等式不成立,那麼n是合數。如果有很多的a能夠使等式成立,那麼我們可以說n可能是質數,或者偽質數。
在我們檢驗過程中,有可能我們選取的a都能讓等式成立,然而n卻是合數。這時等式
被稱為Fermat liar。如果我們選取滿足下面等式的a
那麼a也就是對於n的合數判定的Fermat witness。
a | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
最小的n值 | 4 | 341 | 91 | 15 | 4 | 35 | 6 | 9 | 4 | 9 | 10 | 65 | 4 | 15 | 14 | 15 | 4 | 25 | 6 | 21 | 4 | 21 | 22 | 25 | 4 | 9 | 26 | 9 | 4 | 49 |
算法以及運行時間
整個算法可以寫成是下面兩大部:
- 輸入:n需要檢驗的數;k:參數之一來決定檢驗需要進行的次數。
- 輸出:當n是合數時輸出合數,否則輸出可能是質數:
- 重複k次:
- 在[2, n − 2]範圍內隨機選取a
- 如果an − 1 mod n ≠ 1那麼返回合數
- 返回可能是質數
若使用模指數運算的快速算法,這個算法的運行時間是O(klog2n log log n) = Õ(k log2n),這裏k是一個隨機的a需要檢驗的次數,n是我們想要檢驗的數。
缺點
眾所周知,對於卡米歇爾數n,全部令gcd(a,n)=1的a都是費馬騙子數(Fermat liars)。儘管卡米歇爾數很是稀有,但是卻足夠令費馬質數判定法無法像如米勒-拉賓和Solovay-Strassen的質性檢驗般,成為被經常實際應用的質性檢驗。
一般的,如果n不是卡米歇爾數,那麼至少一半的
是費馬證人數(Fermat witnesses)。在這裏,令a為費馬證人數、a1, a2, ..., as為費馬騙子數。那麼
所有的a×ai for i = 1, 2, ..., s都是費馬證人數。
應用
參見
參考
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Section 31.8: Primality testing. Introduction to Algorithms Second. MIT Press; McGraw-Hill. 2001: 889–890. ISBN 0-262-03293-7.
|