Fermat primality test

The Fermat primality test is a probabalistic test to determine if a number is composite or probably prime.

Fermat's little theorem states that if p is prime and <math>1 \le a \le p<math>, then

<math>a^{p-1} \equiv 1 \pmod{p}<math>.

If we want to test if p is prime, then we can pick random a's in the interval and see if the equality holds. If the equality does not hold for any value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probably prime, or a pseudoprime.

It may be in our tests that we do not pick any value for a such that the equality fails. Any a such that

<math>a^{p-1} \equiv 1 \pmod{p}<math>

when p is composite is known as a Fermat liar. If we do pick an a such that

<math>a^{p-1} \not\equiv 1 \pmod{p}<math>

then a is known as a Fermat witness for the compositeness of n.

Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k × log³p), where k is the number of times we test a random a, and p is the value we want to test for primality.

There are certain values of p known as Carmichael numbers for which all values of a are Fermat liars. Although Carmichael numbers are rare, there are enough of them that Fermat's primality test is often not used in favor of other primality tests such as Miller-Rabin and Solovay-Strassen.

In general, if p is not a Carmichael number then at least half of all

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

are Fermat witnesses. For proof of this let a be a Fermat witness and <math>a_1, a_2, \ldots, a_s<math> be Fermat liars. Then

<math>(a\cdot a_i)^{p-1} \equiv a^{p-1}\cdot a_i^{p-1} \equiv a^{p-1} \not\equiv 1\pmod{p}<math>

and so all <math>a\cdot a_i<math> for <math>i=1, 2,\ldots , s<math> are Fermat witnesses.

The encryption program PGP uses this primality test in its algorithms.