费马素性检验

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

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

。 

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

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

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

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

123456789101112131415161718192021222324252627282930最小的  值43419115435694910654151415425621421222549269449

 算法以及运行时间 

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

若使用模指數運算的快速算法，这个算法的运行时间是 ，这里  是一个随机的  需要检验的次数， 是我们想要检验的数。

 缺点 

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

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

是費馬證人數（Fermat witnesses）。在这里，令  为費馬證人數、 为費馬騙子數。那么

所有的都是費馬證人數。

 应用 

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

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

 参考 


Category:素性测试
Category:同余