費馬質數判定法

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

概念

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

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

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

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

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

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

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

那麼 ${\displaystyle a}$ 也就是對於 ${\displaystyle n}$ 的合數判定的Fermat witness。

${\displaystyle 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
最小的 ${\displaystyle 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

算法以及運行時間

整個算法可以寫成是下面兩大部：

輸入：${\displaystyle n}$ 需要檢定的數；${\displaystyle k}$：參數之一來決定檢定需要進行的次數。

輸出：當 ${\displaystyle n}$ 是合數時輸出合數，否則輸出可能是質數：

重複 ${\displaystyle k}$ 次：

在 ${\displaystyle [2,n-2]}$ 範圍內隨機選取 ${\displaystyle a}$

如果 ${\displaystyle a^{n-1}{\bmod {n}}\neq 1}$ 那麼返回合數

返回可能是質數

若使用模指數運算的快速算法，這個算法的運行時間是 ${\displaystyle {\text{O}}(k\log ^{2}n\log \log n)={\tilde {\text{O}}}(k\log ^{2}n)}$，這裡 ${\displaystyle k}$ 是一個隨機的 ${\displaystyle a}$ 需要檢定的次數，${\displaystyle n}$ 是我們想要檢定的數。

缺點

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

一般的，如果 ${\displaystyle n}$ 不是卡米歇爾數，那麼至少一半的

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

是費馬證人數（Fermat witnesses）。在這裡，令 ${\displaystyle a}$ 為費馬證人數、${\displaystyle a_{1},a_{2},\cdots ,a_{s}}$ 為費馬騙子數。那麼

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

所有的${\displaystyle a\times a_{i}\ {\text{for}}\ i=1,2,\cdots ,s}$都是費馬證人數。

應用

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

參見

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

參考

• Thomas H. Cormen（英語：Thomas H. Cormen）, Charles E. Leiserson（英語：Charles E. Leiserson）, Ronald L. Rivest, Clifford Stein（英語：Clifford Stein）. Section 31.8: Primality testing. Introduction to Algorithms Second. MIT Press; McGraw-Hill. 2001: 889–890. ISBN 0-262-03293-7.