Encyclopedia > Probable prime

Article Content

Probable prime

In number theory, a probable prime (PRP) is an integer that is indicated as prime by Fermat's test for compositeness. While there are probable primes that are composite (these are called pseudoprimes), they are very rare; hence the term probable prime.

Fermat's test, which is based on Fermat's little theorem states the following: given an integer n, choose some integer a coprime to n and calculate a^n-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 primes find application in cryptography. The larger a PRP n is, the less likely it is to be composite. Prime numbers used in cryptography are large enough (currently 512 or 1024 bits) that the chance of their being pseudoprimes is negligibly small. Further, testing for probable primality is significantly faster than deterministic primality tests.

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.