費馬質數判定法

費馬素性檢驗是一種質數判定法則,利用隨機化算法判斷一個數是合數還是可能是素數。

概念

編輯

根據費馬小定理:如果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都是費馬證人數。

應用

編輯

加密程序PGP在算法當中用到了這個素性檢驗方法。

參見

編輯

參考

編輯