費馬素性檢驗
是一種隨機化算法，判斷一個數是合數還是可能是素數。根據費馬小定理：如果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^ \not\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^ \not\equiv 1\pmod</math>
所有的 a × ai for i = 1, 2, ..., s 都是 Fermat witnesses 。
加密程式PGP在算法當中用到了這個素性檢驗方法。
其它
盤點密碼學相關知識
| 盤點密碼學相關知識，密碼學是研究編制密碼和破譯密碼的技術科學。 |
