Probable primes

This article page is a stub, please help by expanding it.

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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{45^{34351} - 1}{44}} , a number of almost 57000 decimal digits, is a probable prime. A number like Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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.