費馬素性檢驗

根據費馬小定理：如果p是素數，

，那麼 ^[1] 

如果我們想知道n是否是素數，我們在中間選取a，看看上面等式是否成立。如果對於數值a等式不成立，那麼n是合數。如果有很多的a能夠使等式成立，那麼我們可以説n可能是素數，或者偽素數。

在我們檢驗過程中，有可能我們選取的a都能讓等式成立，然而n卻是合數。這時等式

被稱為Fermat liar。如果我們選取滿足下面等式的a

那麼a也就是對於n的合數判定的Fermat witness。

整個算法可以寫成是下面兩大部：

返回可能是素數

若使用模指數運算的快速算法，這個算法的運行時間是O(k×logn)，這裏k是一個隨機的a需要檢驗的次數，n是我們想要檢驗的數。

眾所周知，對於卡米歇爾數n，全部的a都會令gcd(a,n)=1，我們稱之為費馬騙子數（Fermat liars）。儘管卡米歇爾數很是稀有，但是卻足夠令費馬素性檢驗無法像如米勒-拉賓和Solovay-Strassen的素性檢驗般，成為被經常實際應用的素性檢驗。

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

是費馬證人數（Fermat witnesses）。在這裏，令a為費馬證人數、a₁,a₂, ...,a_s為費馬騙子數。那麼

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

加密程序PGP在算法當中用到了這個素性檢驗方法。