- Fermat primality test
The

**Fermat primality test**is a probabilistic test to determine if a number is probably prime.**Concept**Fermat's little theorem states that if "p" is prime and $1\; le\; a\; <\; p$, then:$a^\{p-1\}\; equiv\; 1\; pmod\{p\}$

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

:$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

:$a^\{n-1\}\; otequiv\; 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__:return__probably prime__Using fast algorithms for

modular exponentiation , the running time of this algorithm is O("k" × log^{2}"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.**Flaws**There are certain values of "n" known as

Carmichael number s 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 otherprimality test s such as Miller-Rabin and Solovay-Strassen.In general, if "n" is not a Carmichael number then at least half of all

:$ain(mathbb\{Z\}/nmathbb\{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:$(acdot\; a\_i)^\{n-1\}\; equiv\; a^\{n-1\}cdot\; a\_i^\{n-1\}\; equiv\; a^\{n-1\}\; otequiv\; 1pmod\{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. The chance of PGP generating a Carmichael number is less than 1 in 10

^{50}, which is more than adequate for practical purposes.**References***

Thomas H. Cormen ,Charles E. Leiserson ,Ronald L. Rivest , andClifford 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.

*Wikimedia Foundation.
2010.*