# Fermat primality test

The **Fermat primality test** is a probabilistic test to determine if a number is composite or *probably* prime.

## Concept

Fermat's little theorem states that if *p* is prime and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \le a < p}**
, then

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{p-1} \equiv 1 \pmod{p}}**.

If we want to test if *n* is prime, then we can pick random *a'*s in the interval and see if the equality holds. If the equality does not hold for a value of *a*, then *n* is composite. If the equality does hold for many values of *a*, then we can say that *n* is probably prime, or a pseudoprime.

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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{n-1} \equiv 1 \pmod{n}}**

when *n* is composite is known as a *Fermat liar*. If we do pick an *a* such that

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{n-1} \not\equiv 1 \pmod{n}}**

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

## 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}mod*n*≠ 1 then return__composite__

- pick
- return
__probably prime__

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

## Flaws

There are certain values of *n* known as Carmichael numbers for which __all__ values of *a* for which gcd(a,n)=1 are Fermat liars. Although Carmichael numbers are rare, there are enough of them that Fermat's primality test is often not used in favor of other primality tests such as Miller-Rabin and Solovay-Strassen.

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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 *a* × *a*_{i} for *i* = 1, 2, ..., *s* are Fermat witnesses.

## Usage

The encryption program PGP uses this primality test in its algorithms.

## References

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
*Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 889–890 of section 31.8, Primality testing.