Fermat primality test

From Wikipedia, the free encyclopedia

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

Contents 1 Concept 2 Example 3 Algorithm and running time 4 Flaws 5 Usage 6 References

[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 probably prime, or a pseudoprime.

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. 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 of a = 38. Check the above equality:

Either 221 is prime, or 38 is a Fermat liar, so we take another a of 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 × log²n × 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] 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

are Fermat witnesses. For proof of this, let a be a Fermat witness and a₁, a₂, ..., a_s be Fermat liars. Then

and so all a × a_i for i = 1, 2, ..., s are Fermat witnesses.

[edit] Usage

The encryption program PGP uses this primality test in its algorithms. The chance of PGP generating a Carmichael number is less than 1 in 10⁵⁰, which is more than adequate for practical purposes.

[edit] 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 0-262-03293-7. Pages 889–890 of section 31.8, Primality testing.

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie–PSW · ECPP · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P − 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Schoof's · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.