费马素性检验

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

概念 
根据费马小定理：如果p是素数，，那么

。 

如果我们想知道n是否是素数，我们在中间选取a，看看上面等式是否成立。如果对于数值a等式不成立，那么n是合数。如果有很多的a能够使等式成立，那么我们可以说n可能是素数，或者伪素数。

在我们检验过程中，有可能我们选取的a都能让等式成立，然而n却是合数。这时等式

被称为Fermat liar。如果我们选取满足下面等式的a 

那么a也就是对于n的合数判定的Fermat witness。

算法以及运行时间 

整个算法可以写成是下面两大部：
输入：n需要检验的数；k：参数之一来决定检验需要进行的次数。
输出：当n是合数时輸出合数，否则輸出可能是素数：
重复k次：
在[2, n − 2]范围内随机选取a
如果an − 1 mod n ≠ 1那么返回合数
返回可能是素数

若使用模指數運算的快速算法，这个算法的运行时间是O(klog2n log log n) = Õ(k log2n)，这里k是一个随机的a需要检验的次数，n是我们想要检验的数。

缺点 

众所周知，对于卡米歇爾數n，全部令gcd(a,n)=1的a都是費馬騙子數（Fermat liars）。尽管卡米歇爾數很是稀有，但是却足够令费马素性检验无法像如米勒-拉賓和Solovay-Strassen的素性检验般，成為被经常實際应用的素性检验。 

一般的，如果n不是卡米歇爾數，那么至少一半的

是費馬證人數（Fermat witnesses）。在这里，令a为費馬證人數、a1, a2, ..., as为費馬騙子數。那么

所有的a×ai for i = 1, 2, ..., s都是費馬證人數。

应用 

加密程序PGP在算法当中用到了这个素性检验方法。

参见 
 卢卡斯-莱默检验法
 埃拉托斯特尼筛法
 米勒-拉宾检验
 试除法
孪生素数
三胞胎素数
四胞胎素数
素数判定法则
表兄弟素数
六素数
X²+1素数

参考 
 

素性测试
同余