Fermat primality test

The Fermat primality test is a probabilistic test to determine whether a number is probable prime.

Concept

Fermat's little theorem states that if p is prime and 0 < a < p, then

a^{p-1} \equiv 1 \pmod{p}.

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

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

a^{n-1} \equiv 1 \pmod{n}

when n is composite is known as a Fermat liar. Vice versa, in this case n is called Fermat pseudoprime to base a.

If we do pick an a such that

a^{n-1} \not\equiv 1 \pmod{n}

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

Example

Suppose we wish to determine whether n = 221 is prime. Randomly pick 0 < a < 221, say a = 38. We check the above equality and find that it holds:

a^{n-1} = 38^{220} \equiv 1 \pmod{221}.

Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 24:

a^{n-1} = 24^{220} \equiv 81 \not\equiv 1 \pmod{221}.

So 221 is composite and 38 was indeed a Fermat liar.

Algorithm and running time

The algorithm can be written as follows:

Inputs: n: a value to test for primality; k: a parameter that determines the number of times to test for primality
Output: composite if n is composite, otherwise probably prime
Repeat k times:
Pick a randomly in the range [1, n − 1]
If a^{n-1}\not\equiv1 \pmod n, then return composite
If composite is never returned: return probably prime

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

Flaw

There are infinitely many values of n (known as Carmichael numbers) for which all values of a for which gcd(a, n) = 1 are Fermat liars. While Carmichael numbers are substantially rarer than prime numbers,[1] there are enough of them that Fermat's primality test is often not used in the above form. Instead, other more powerful extensions of the Fermat test, such as Baillie-PSW, Miller-Rabin, and Solovay-Strassen are more commonly used.

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

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

are Fermat witnesses. For proof of this, let a be a Fermat witness and a_1, a_2, ..., a_s be Fermat liars. Then

(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}

and so all a \times a_i for i = 1, 2, ..., s are Fermat witnesses.

Applications

In practice the Fermat test is combined with other primality tests to generate a random number, which is prime with sufficiently high probability. GNU Privacy Guard uses a combination of trial division by small prime numbers, then a Fermat test and finally a Miller-Rabin test to test for primality.[2] Similar approaches are used by PGP and OpenSSL.

References

  1. ↑ Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n)
  2. ↑ http://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=blob;f=cipher/primegen.c;h=9f6ec7055977163681838803a4f298235c1ab8c2;hb=HEAD#l852