Fermat primality test
Definition
The Fermat primality test is a quick and often inconclusive primality test. In the version below, we consider only .
Given a natural number , the test works as follows:
- Pick a random element
from the congruence classes of nonzero integers mod
(exclude the congruence class of 0). Explicitly, pick
as an integer among
.
- Check whether
. To compute the power use repeated squaring. If the condition does not hold, then
is composite. If the condition does hold, then
may be prime or composite.
The above is a single iteration of the test. Multiple iterations of the test may be carried out with multiple random elements. If at any stage the condition is violated, we can conclude that the number is composite. If, however, the condition holds every time, the situation is inconclusive and
may be prime or composite.
Theory
Why it works
The primality test above is correct because of Fermat's little theorem, which says that for a prime and
relatively prime to
, we have:
Behavior on composite numbers
For any composite number , we use the following terms:
- A Fermat witness for
is a value
such that
.
- A Fermat liar for
is a value
such that
.
- We say that
is a Fermat pseudoprime to base
if
is a Fermat liar for
.
Nonzero numbers that have a common factor with always serve as Fermat witnesses. There are
of these where
is the Euler totient function. For
composite, this number is at least equal to
, the worst case arising when
is a square of a prime. In general, if
has a small number of large prime factors, there are very few such numbers and a uniform random choice is highly unlikely to hit them.
For the numbers that are relatively prime to , we have the formula for probability of relatively prime integer being a Fermat liar. If the probability is 1, then
is a Carmichael number. If the probability is less than 1, then it is at most 1/2, which means that the Fermat primality test can find a witness with arbitrarily high probability of success in a finite number of trials.