Fermat's primality test

How the test works

The basic routine is easy to describe and implement. For a chosen base a (1 < a < n):

• Compute a^(n-1) mod n using fast modular exponentiation.
• If the result is not 1, n is composite.
• If the result is 1, n is a probable prime to base a (a Fermat probable prime).

Repeated tests with different bases reduce the chance of a composite number passing by accident. Many implementations use several random or selected bases to increase confidence. See further notes at more about the algorithm.

Limitations and pseudoprimes

Fermat's test is fast but imperfect. Some composite numbers satisfy a^(n-1) ≡ 1 (mod n) for many or all a coprime to n; such numbers are called Carmichael numbers and can fool the test into declaring a composite as probable prime. A number that passes the test for a particular base a is called a Fermat pseudoprime to base a. For guidance see Carmichael numbers and related material.

History and practical use

The test dates to ideas around Fermat's little theorem and has been used since early computational number theory as a rapid first filter in primality screening. It remains useful where very fast, low-cost checks are needed, for example as a preliminary step before applying stronger tests. However, because of false positives it is not recommended alone for cryptographic key generation; deterministic or stronger probabilistic tests such as the Miller–Rabin strong probable prime test are preferred. Further resources and comparisons are available at detailed references.

Notable facts: the test is very quick in practice because modular exponentiation can be done in polynomial time. Its simplicity makes it a useful educational tool and a stepping stone to more robust primality algorithms.