Probable primes

Probable primes are numbers which are strongly believed to be prime numbers, but may be beyond the reach of today's implemented primality algorithms.

For example, ${\displaystyle {\frac {45^{34351}-1}{44}}}$, a number of almost 57000 decimal digits, is a probable prime. A number like ${\displaystyle 2^{2^{127}-1}-1}$, on the other hand, might be prime, but it could just as easily be composite like the majority of small Mersenne numbers, and is thus not considered a probable prime.

One reason to believe with great certainty that a given number is prime is if it is certified to be a pseudoprime to many different bases. Such a number could be a Carmichael number, but given the low density of Carmichael numbers and the much higher density of prime numbers, it would be more reasonable to believe such a number to be prime.

External links

• Chris Caldwell, "probable prime", The Prime Glossary
• Eric W. Weisstein, "Probable Prime." From MathWorld--A Wolfram Web Resource.