费马素性检验

费马素性检验是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。

概念

根据费马小定理：如果 $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}{\bmod {n}}\neq 1$ 那么返回合数

返回可能是素数

若使用模指數運算的快速算法，这个算法的运行时间是 ${\text{O}}(k\log ^{2}n\log \log n)={\tilde {\text{O}}}(k\log ^{2}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_{1},a_{2},\cdots ,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\times a_{i}\ {\text{for}}\ i=1,2,\cdots ,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.