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

根据费马小定理：如果p是素数，<math>1 \\le a \\le p</math>，那么

<math>a^ \\equiv 1 \\pmod</math>。

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

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

<math>a^ \\equiv 1 \\pmod</math>

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

<math>a^ \ot\\equiv 1 \\pmod</math>

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

整个算法可以写成是下面两大部：

输入：n需要检验的数；k：参数之一来决定检验需要进行的次数。

输出：当n是合数时，否则可能是素数：

重复k次：

在[1, n − 1]范围内随机选取a

如果an − 1 mod n ≠ 1 那么返回合数

返回可能是素数

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

众所周知，对于卡米歇尔数n，全部的a都会令gcd(a,n)=1，我们称之为fermat liars。尽管卡米歇尔数很是稀有，但是却足够令费马素性检验无法像如米勒-拉宾和Solovay-Strassen的素性检验般，成为被经常实际应用的素性检验。

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

<math>a\\in(\\mathbb/n\\mathbb)^*</math>

是 Fermat witnesses。在这里，令 a 为Fermat witness 、 a1, a2, ..., as 为 Fermat liars。那么

<math>(a\\cdot a_i)^ \\equiv a^\\cdot a_i^ \\equiv a^ \ot\\equiv 1\\pmod</math>

所有的 a × ai for i = 1, 2, ..., s 都是 Fermat witnesses 。

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