This site is supported by donations to The OEIS Foundation.

Probable primes

From OeisWiki

Jump to: navigation, search

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, \frac{45^{34351} - 1}{44}, a number of almost 57000 decimal digits, is a probable prime. A number like 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

Personal tools