The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
Fermat's little theorem states that if p is prime and a is not divisible by p, then
If one wants to test whether p is prime, then we can pick random integers a not divisible by p and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a if p is composite. Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime.
However, note that the above congruence holds trivially for , because the congruence relation is compatible with exponentiation. It also holds trivially for if p is odd, for the same reason. That is why one usually chooses a random a in the interval .
Any a such that
when n is composite is known as a Fermat liar. In this case n is called Fermat pseudoprime to base a.
If we do pick an a such that
then a is known as a Fermat witness for the compositeness of n.
Suppose we wish to determine whether n = 221 is prime. Randomly pick 1 < a < 220, say a = 38. We check the above congruence and find that it holds:
Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 24:
So 221 is composite and 38 was indeed a Fermat liar. Furthermore, 24 is a Fermat witness for the compositeness of 221.
The algorithm can be written as follows:
Inputs: n: a value to test for primality, n>3; 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 [2, n − 2]
If , then return composite
If composite is never returned: return probably prime
The a values 1 and n-1 are not used as the equality holds for all n and all odd n respectively, hence testing them adds no value.
Using fast algorithms for modular exponentiation and multiprecision multiplication, the running time of this algorithm is O(k log2n log log n) = Õ(k log2n), where k is the number of times we test a random a, and n is the value we want to test for primality; see Miller–Rabin primality test for details.