Fermat primality test
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
Concept
Fermat's little theorem states that if p is prime and a is not divisible by p, then
- [math]\displaystyle{ a^{p-1} \equiv 1 \pmod{p}. }[/math]
If one wants to test whether p is prime, then we can pick random integers a not divisible by p and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a if p is composite.[1] Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime.
However, note that the above congruence holds trivially for [math]\displaystyle{ a \equiv 1 \pmod{p} }[/math], because the congruence relation is compatible with exponentiation. It also holds trivially for [math]\displaystyle{ a \equiv -1 \pmod{p} }[/math] if p is odd, for the same reason. That is why one usually chooses a random a in the interval [math]\displaystyle{ 1 \lt a \lt p - 1 }[/math].
Any a such that
- [math]\displaystyle{ a^{n-1} \equiv 1 \pmod{n} }[/math]
when n is composite is known as a Fermat liar. In this case n is called Fermat pseudoprime to base a.
If we do pick an a such that
- [math]\displaystyle{ a^{n-1} \not\equiv 1 \pmod{n} }[/math]
then a is known as a Fermat witness for the compositeness of n.
Example
Suppose we wish to determine whether n = 221 is prime. Randomly pick 1 < a < 220, say a = 38. We check the above congruence and find that it holds:
- [math]\displaystyle{ a^{n-1} = 38^{220} \equiv 1 \pmod{221}. }[/math]
Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 24:
- [math]\displaystyle{ a^{n-1} = 24^{220} \equiv 81 \not\equiv 1 \pmod{221}. }[/math]
So 221 is composite and 38 was indeed a Fermat liar. Furthermore, 24 is a Fermat witness for the compositeness of 221.
Algorithm
The algorithm can be written as follows:
- Inputs: n: a value to test for primality, n>3; 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 [2, n − 2]
- If [math]\displaystyle{ a^{n-1}\not\equiv1 \pmod n }[/math], then return composite
- If composite is never returned: return probably prime
The a values 1 and n-1 are not used as the equality holds for all n and all odd n respectively, hence testing them adds no value.
Complexity
Using fast algorithms for modular exponentiation and multiprecision multiplication, the running time of this algorithm is O(k log2n log log n) = Õ(k log2n), where k is the number of times we test a random a, and n is the value we want to test for primality; see Miller–Rabin primality test for details.
Flaw
There are infinitely many Fermat pseudoprimes to any given basis a>1.[1]:Theorem 1
Even worse, there are infinitely many Carmichael numbers.[2] These are numbers [math]\displaystyle{ n }[/math] for which all values of [math]\displaystyle{ a }[/math] with [math]\displaystyle{ \operatorname{gcd}(a, n) = 1 }[/math] are Fermat liars. For these numbers, repeated application of the Fermat primality test performs the same as a simple random search for factors. While Carmichael numbers are substantially rarer than prime numbers (Erdös' upper bound for the number of Carmichael numbersCite error: Closing </ref>
missing for <ref>
tag
As an exception, OpenPFGW uses only the Fermat test for probable prime testing. The program is typically used with multi-thousand digit inputs with a goal of maximum speed with very large inputs. Another well known program that relies only on the Fermat test is PGP where it is only used for testing of self-generated large random values (an open source counterpart, GNU Privacy Guard, uses a Fermat pretest followed by Miller–Rabin tests).
References
- ↑ 1.0 1.1 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109". Mathematics of Computation 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. //math.dartmouth.edu/~carlp/PDF/paper25.pdf.
- ↑ Alford, W. R.; Granville, Andrew; Pomerance, Carl (1994). "There are Infinitely Many Carmichael Numbers". Annals of Mathematics 140 (3): 703–722. doi:10.2307/2118576. http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 31.8: Primality testing". Introduction to Algorithms (Second ed.). MIT Press; McGraw-Hill. p. 889–890. ISBN 0-262-03293-7.
Original source: https://en.wikipedia.org/wiki/Fermat primality test.
Read more |