Probable prime
|
|
In number theory, a probable prime (PRP) is an integer that satisfies a condition also satisfied by all prime numbers. While there are probable primes that are composite (called pseudoprimes), they are rare, depending on the test used.
Fermat's test for compositeness, which is based on Fermat's little theorem states the following: given an integer n, choose some integer a coprime to n and calculate an − 1 modulo n. If the result is different from 1, n is composite. If it is 1, n may or may not be prime; n is then called a weak probable prime base a.
Fermat's test may be improved by using the fact that the only square roots of 1 modulo a prime are 1 and −1. Numbers indicated prime by this stronger test are known as strong probable primes (SPRP) base a .
An Euler probable prime is an integer that is indicated prime by the somewhat stronger theorem that for any prime p, and any a, a(p − 1)/2 equals (a/p) modulo p, where (a/p) is the Legendre symbol. This test is equally efficient but is twice as strong as Fermat's test. An Euler probably prime which is composite is called an Euler-Jacobi pseudoprime.
Probable primality is a basis for efficient primality testing algorithms, which find application in cryptography. These algorithms are usually probabilistic in nature. The idea is that while there are composite base a probable primes for any fixed a, we may reverse the roles: for any fixed composite n and a randomly chosen a, we can hope that n is not a base a pseudoprime, with high probability.
This is unfortunately false for weak probable primes, because there exist Carmichael numbers; but it is true for more refined notions of probable primality, such as strong probable primes (we get the Miller-Rabin algorithm), or Euler probable primes (Solovay-Strassen algorithm).
Even when a deterministic primality proof is required, a useful first step is to test for probable primality.
A PRP test is sometimes combined with a table of small pseudoprimes to quickly establish the primality of a given number smaller than some threshold.
See also
External links
- The prime glossary - Probable prime (http://primes.utm.edu/glossary/page.php?sort=PRP)
- The PRP Top 10000 (the largest known probable primes) (http://www.primenumbers.net/prptop/)fr:Nombre premier probable