費馬質數判定法

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

概念

根據費馬小定理：如果p是素數，$1\leq a\leq p-1$，那麼

$a^{p-1}\equiv 1{\pmod {p}}$。

如果我們想知道n是否是素數，我們在中間選取a，看看上面等式是否成立。如果對於數值a等式不成立，那麼n是合數。如果有很多的a能夠使等式成立，那麼我們可以說n可能是素數，或者偽素數。

在我們檢驗過程中，有可能我們選取的a都能讓等式成立，然而n卻是合數。這時等式

$a^{n-1}\equiv 1{\pmod {n}}$

被稱為Fermat liar。如果我們選取滿足下面等式的a

$a^{n-1}\not \equiv 1{\pmod {n}}$

那麼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

如果a^{n − 1} mod n ≠ 1那麼返回合數

返回可能是素數

若使用模指數運算的快速算法，這個算法的運行時間是O(klog²n log log n) = Õ(k log²n)，這裡k是一個隨機的a需要檢驗的次數，n是我們想要檢驗的數。

缺點

眾所周知，對於卡米歇爾數n，全部令gcd(a,n)=1的a都是費馬騙子數（Fermat liars）。儘管卡米歇爾數很是稀有，但是卻足夠令費馬素性檢驗無法像如米勒-拉賓和Solovay-Strassen的素性檢驗般，成為被經常實際應用的素性檢驗。

一般的，如果n不是卡米歇爾數，那麼至少一半的

$a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$

是費馬證人數（Fermat witnesses）。在這裡，令a為費馬證人數、a₁, a₂, ..., a_s為費馬騙子數。那麼

$(a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}$

所有的a×a_i for i = 1, 2, ..., s都是費馬證人數。

應用

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

參見

• 盧卡斯-萊默檢驗法
• 埃拉托斯特尼篩法
• 米勒-拉賓檢驗
• 試除法
• 孿生素數
• 三胞胎素數
• 四胞胎素數
• 素數判定法則
• 表兄弟素數
• 六素數
• X²+1素數

參考

• 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.