How far is the list of known primes known to be complete?

Question

So there is always the search for the next "biggest known prime number". The last result that came out of GIMPS was $2^{74\,207\,281} - 1$, with over twenty million digits. Wikipedia also lists the twenty highest known prime numbers, only the four smallest on that list have fewer than three million digits.

For some while now, I have been wondering about the smaller prime numbers we haven't found. How far up is the list of known primes known to be complete? Since $500$ to $1000$ digit primes are considered safe for the RSA algorithm, I'd assume that it's well below that. How far along the number line have we checked that there are no more primes to be found? How fast is this boundary moving forward, currently? Have we, for instance, checked the primality of all numbers below $10^{100}$, or are we stuck somewhere south of $10^{20}$?

Answer 1

The maximum of such list is far smaller than mentioned 500-digits. Due to the prime number theorem $\pi(x) \approx x/\log(x)$ so one could estimate that the list of prime numbers up to $x$ would require at the order of $x$ digits to represent.

So by using the sieve of Atkin the complexity is $O(x)$ for both time consumption and memory consumption. And all memory available is small enough to be feasible to traverse. This means that the memory available for storing such a list is what should be the limiting factor.

Basically this boils down to that the largest such list is as large as anybody have place (and need) for.

Now the total global storage is estimated to be at the order of $10^{21}$ bytes which means that the upper bound of such a prime number list is there. So there exist no complete list with primenumbers up to more than about twenty digits (and not even that since not all storage is devoted to store prime numbers).

Answer 2

This may be a somewhat unsatisfying answer, but no-one's really keeping a complete list of known primes (to the best of my knowledge). Moreover, it's fairly easy to come up with large primes, and it's fairly easy to "guarantee" (guarantee being a slippery term), that a given large number is prime.

The Miller-Rabin primality test is an algorithm that takes a number $n$, and a "certainty" parameter $m$, and (in layman's terms) if $n$ is prime, it will return "PRIME". If $n$ is composite, it will almost certainly (again, a slippery term) return "COMPOSITE", but there's a small probability $(\frac{1}{4^m})$ that it will return "PRIME".

However, by setting $m$ high enough, to, say, something greater than 40, then it essentially means the probability of a composite number being declared prime is smaller than you winning the jackpot in the lottery twice in one week. Thus, for almost ALL practical purposes, it suffices to work with primes that pass the Miller-Rabin test to a high degree of certainty. Henri Cohen famously called such numbers "Industrial Grade Primes".

If you're still interested in having "proof" that a number is prime, may I suggest reading up on prime certificates. I haven't ever personally come across a situation in which you'd prefer a certified prime to an industrial grade prime however.

Finally, as a quick example, Mathematica can generate very large primes easily. The Mathematica command "RandomPrime[{10^1000, 10^1001}]" generates a random 1000 digit prime in 0.40625 seconds on my five year old desktop machine. This should give you some indication as to why mathematicians generally don't keep long lists of all known primes.

Answer 3

It seems that this link, provided by Yuriy S in the comments above more or less addresses my question. It states that prime gap searches have checked the primality (but not stored the primes) for all numbers up to about 20 digits (the exact bound is always changing, since the numbers are relatively small).

Answer 4

Listing primes in order is a fairly trivial problem — in fact, I believe we have programs that can compute lists of primes faster than they can be written to disk, let alone displayed in any human readable format.

The thing is, there are a lot of primes. The entire internet put together probably couldn't store the list of all 20 digit primes.

But that's okay, because we don't need lists of primes — whenever we need primes, we can just generate them.

Answer 5

First, what is a "list of primes"? It's some fixed storage in a format that would allow me to know all members of an arbitrary set S of integers, for the special case that S is a subrange of the set of primes. For example "11, 13, 17, 19" is a list of primes. Given this list (and if you trust me) you can know four consecutive primes.

You can store a list of primes in a quite compact way. For example, just store the first prime in the list, followed by the differences between each prime and the next prime, compressed with a good compression algorithm. In my example, "11,2,4,2" would represent 11, 11+2 = 13, 13+4 = 17, 17+2 = 19. I would estimate that you can store a large list of primes using about 1 byte per prime.

Now I just bought a 4TB hard drive for about £70. So at a cost of £70 I can store a list of about 4 trillion primes. If I wanted to store the largest list I'd spend £100,000 (my wife would kill me) for 1,400 such hard drives and store a list of almost 6 quadrillion bytes. And that would probably be the largest complete list of known primes because ...

... because nobody in their right mind would do that! If you wanted the first billion primes greater than one quadrillion, I wouldn't read my list from one of these hard drives. I would create a prime sieve in the memory of my computer and calculate it on the spot. Cheaper and faster than reading a list.

You will find lists of special primes. Say "complete list of known primes of the form $2^n-1$ for some integer n ≥ 1". But storing a list of all primes is just nonsense.

PS. These 6 quadrillion bytes at a cost of £100,000, at about 1 byte per prime due to compression, could store a list of primes up to $120 \cdot 10^{15}$. I'd be willing to send you a list of primes up to $80 \cdot 10^{12}$ on a large hard drive for say $500, which would pay for some of the cost creating the list.

PPS. A "list" of known primes would have to be recorded. A number x that has at some point be determined to be a prime is not a "known prime" if it is not recorded. (Given a list of known primes, I can determine whether x is prime or not by checking that it would be in the list if it was prime due to the list size, and then checking whether it is on the list. If nobody recorded that x is prime then I cannot do this). And nobody records large lists of known primes because it is pointless. You wouldn't use a list to determine if x is prime.