Fermat primality test
Encyclopedia
The Fermat primality test is a probabilistic
test to determine if a number is probable prime
.
states that if p is prime and
, then
If we want to test if p is prime, then we can pick random as in the interval and see if the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probable prime
.
It might be in our tests that we do not pick any value for a such that the equality fails. Any a such that
when n is composite is known as a Fermat liar. Vice versa, 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.
Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 26:
So 221 is composite and 38 was indeed a Fermat liar.
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
, then return composite
return probably prime
Using fast algorithms for modular exponentiation
, 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.
(known as Carmichael numbers) for which all values of 
for which 
are Fermat liars. While Carmichael numbers are substantially rarer than prime numbers, there are enough of them that Fermat's primality test is often not used in favor of other primality test
s such as Miller-Rabin
and Solovay-Strassen
.
In general, if
is not a Carmichael number then at least half of all
are Fermat witnesses. For proof of this, let
be a Fermat witness and 
, 
, ..., 
be Fermat liars. Then
and so all
for 
are Fermat witnesses.
uses this primality test in its algorithms. The chance of PGP generating a Carmichael number is less than 1 in 1050, which is more than adequate for practical purposes.
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
test to determine if a number is probable prime
Probable prime
In number theory, a probable prime is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions...
.
Concept
Fermat's little theoremFermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
states that if p is prime and
, thenIf we want to test if p is prime, then we can pick random as in the interval and see if the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probable prime
Probable prime
In number theory, a probable prime is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions...
.
It might be in our tests that we do not pick any value for a such that the equality fails. Any a such that
when n is composite is known as a Fermat liar. Vice versa, 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.
Example
Suppose we wish to determine if n = 221 is prime. Randomly pick 1 ≤ a < 221, say a = 38. Check the above equality:Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 26:
So 221 is composite and 38 was indeed a Fermat liar.
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
, then return compositereturn probably prime
Using fast algorithms for modular exponentiation
Modular exponentiation
Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....
, the running time of this algorithm is O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(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.
Flaw
There are infinitely many values of (known as Carmichael numbers) for which all values of for which are Fermat liars. While Carmichael numbers are substantially rarer than prime numbers, there are enough of them that Fermat's primality test is often not used in favor of other primality testPrimality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
s such as Miller-Rabin
Miller-Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithmwhich determines whether a given number is prime,...
and Solovay-Strassen
Solovay-Strassen primality test
The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime...
.
In general, if
is not a Carmichael number then at least half of allare Fermat witnesses. For proof of this, let
be a Fermat witness and , , ..., be Fermat liars. Thenand so all
for are Fermat witnesses.Applications
The encryption program PGPPretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...
uses this primality test in its algorithms. The chance of PGP generating a Carmichael number is less than 1 in 1050, which is more than adequate for practical purposes.