费马素性检验

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

概念
根据费马小定理：如果 p 是素数，1 \le a \le 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。

算法以及运行时间
整个算法可以写成是下面两大部：
:输入：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素数

参考
*