费马素性检验

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

概念

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