费马素性检验

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

概念

根据费马小定理：如果 ${\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.