# Fermat primality test

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

## Concept

Fermat's little theorem states that if p is prime and a is not divisible by p, then

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

If we want to test whether p is prime, then we can pick random integers a not divisible by p and see whether the equality holds. If the equality 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 for ${\displaystyle a\equiv 1{\pmod {p}}}$, the above congruence holds trivially. It also holds trivially if p is odd and ${\displaystyle a\equiv -1{\pmod {p}}}$. For this reason, one usually chooses a number a in the interval ${\displaystyle 1.

Any a such that

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

when n is composite a 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

${\displaystyle 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 1 < a < 221, say a = 38. We check the above equality and find that it holds:

${\displaystyle 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:

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

So 221 is composite and 38 was indeed a Fermat liar. Furthermore, 24 is a Fermat witness for the compositeness of 221.

## Algorithm and running time

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 ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$, 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 × 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; see Miller–Rabin primality test for details.

## Flaw

First, there are infinitely many Fermat pseudoprimes.

A more serious flaw is that there are infinitely many Carmichael numbers. These are numbers ${\displaystyle n}$ for which all values of ${\displaystyle a}$ with ${\displaystyle gcd(a,n)=1}$ are Fermat liars. For these numbers, repeated application of the Fermat primality test performs the same as a simple random search for factors. While Carmichael numbers are substantially rarer than prime numbers (Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n))[1] there are enough of them that Fermat's primality test is not often 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 ${\displaystyle n}$ is a composite number that is not a Carmichael number, then at least half of all

${\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$ (i.e. ${\displaystyle gcd(a,n)=1}$)

are Fermat witnesses. For proof of this, let ${\displaystyle a}$ be a Fermat witness and ${\displaystyle a_{1}}$, ${\displaystyle a_{2}}$, ..., ${\displaystyle a_{s}}$ be Fermat liars. Then

${\displaystyle (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 ${\displaystyle a\times a_{i}}$ for ${\displaystyle i=1,2,...,s}$ are Fermat witnesses.

## Applications

As mentioned above, most applications use a Miller-Rabin or Baillie-PSW test for primality. Sometimes a Fermat test (along with some trial division by small primes) is performed first to improve performance. GMP since version 3.0 uses a base-210 Fermat test after trial division and before running Miller-Rabin tests. Libgcrypt uses a similar process with base 2 for the Fermat test, but OpenSSL does not.

In practice with most big number libraries such as GMP, the Fermat test is not noticeably faster than a Miller-Rabin test, and can be slower for many inputs.[2]

As an exception, OpenPFGW uses only the Fermat test for probable prime testing. The program is typically used with multi-thousand digit inputs with a goal of maximum speed with very large inputs. Another well known program that relies only on the Fermat test is PGP where it is only used for testing of self-generated large random values (an open source counterpart, GNU Privacy Guard, uses a Fermat pretest followed by Miller-Rabin tests).

## References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 31.8: Primality testing". Introduction to Algorithms (Second ed.). MIT Press; McGraw-Hill. p. 889–890. ISBN 0-262-03293-7.CS1 maint: Multiple names: authors list (link)
1. ^ Paul Erdős (1956). "On pseudoprimes and Carmichael numbers". Publ. Math. Debrecen. 4: 201–206.
2. ^ Joe Hurd (2003), Verification of the Miller-Rabin Probabilistic Primality Test, p. 2