Fermat primality test
The Fermat primality test is a probabilistic test to determine if a number is probable prime.
Contents |
[edit] Concept
Fermat's little theorem states that if p is prime and , then
If we want to test if p 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 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.
[edit] 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.
[edit] 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 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.
[edit] Flaw
There are infinitely many values of n (known as Carmichael numbers) for which all values of a for which gcd(a,n) = 1 are Fermat liars. While Carmichael numbers are substantially rarer than prime numbers,[1] 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
are Fermat witnesses. For proof of this, let a be a Fermat witness and a1, a2, ..., as be Fermat liars. Then
and so all for i = 1,2,...,s are Fermat witnesses.
[edit] Applications
The encryption program PGP 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.
[edit] References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 31.8: Primality testing". Introduction to Algorithms (Second Edition ed.). MIT Press; McGraw-Hill. p. 889–890. ISBN 0-262-03293-7.
- ^ Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n)
|