Fermat primality test

From Example Problems
Jump to navigation Jump to search

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 an − 1 mod n ≠ 1 then return composite
return probably prime

Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k × log3n), 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 a1, a2, ..., as 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 × ai for i = 1, 2, ..., s are Fermat witnesses.

Usage

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

References