54
$\begingroup$

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}$?

$\endgroup$
  • 7
    $\begingroup$ Just as a start, here is First fifty million primes $\endgroup$ – Yuriy S Jul 7 '16 at 10:49
  • 8
    $\begingroup$ @YuriyS I don't want the list. I want to know how long the (longest) list (we can currently make) is. $\endgroup$ – Arthur Jul 7 '16 at 10:51
  • 4
    $\begingroup$ @barakmanos According to wiki (the list I linked in the question) it is $19249×2^{13\,018\,586} + 1$, which is just shy of $4$ million digits, and there are $11$ known Mersenne primes that are larger. $\endgroup$ – Arthur Jul 7 '16 at 10:55
  • 17
    $\begingroup$ @Arthur, here is exactly your question considered $\endgroup$ – Yuriy S Jul 7 '16 at 10:57
  • 3
    $\begingroup$ @joriki: I agree, but I can only delete mine, which would leave this thread kind of enigmatic, so if you have the privilege of doing it, then please go ahead, I will not bare a grudge for that :) $\endgroup$ – barak manos Jul 7 '16 at 11:05
39
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Excellent line of reasoning. If you can't store it, you can't (continue to) know it. Astonishing remindee of the power of exponents... $\endgroup$ – Floris Jul 8 '16 at 1:28
  • 1
    $\begingroup$ Suppose someone with extremely many huge hard disks kept a list of all prime numbers with at most 21 decimal digits. It would be extremely easy to come up with a continuation of that list. For example the first prime over $10^{21}$ (i.e. 22 digits) is $1{,}000{,}000{,}000{,}000{,}000{,}000{,}117$. It takes a few milliseconds to find and prove with standard math software (I used PARI/GP). $\endgroup$ – Jeppe Stig Nielsen Jul 8 '16 at 8:26
22
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ so RSA uses "Industrial Grade Primes" right ? $\endgroup$ – Gabriel Romon Jul 7 '16 at 11:31
  • 2
    $\begingroup$ @skyking Best two I know of are: 1) the elliptic curve primality test, which is $O((\log(n))^6)$, on the condition that certain (probably true) conjectures are true, and 2) Miller's test, upon which the Miller-Rabin test is based, which is a deterministic test. It only works under the assumption of GRH, but it works in $O((\log(n))^4 \log^k((\log(n))^4)$, for some integer $k$. $\endgroup$ – MadMonty Jul 7 '16 at 14:23
  • 5
    $\begingroup$ "I haven't ever personally come across a situation in which you'd prefer a certified prime to an industrial grade prime"; one case might be if you're generating a prime for a long term DH group (e.g. IKE group 14) or EC curve (e.g. P256 or Curve25519); since such a group/curve might be used literally billions of times, it might make sense to go to the extra effort of doing the full certification. $\endgroup$ – poncho Jul 7 '16 at 16:54
  • 9
    $\begingroup$ Are there any Industrial Grade Primes that are known to be composite? $\endgroup$ – Plutor Jul 7 '16 at 18:10
  • 2
    $\begingroup$ @MadMonty The AKS primality test is deterministic, its correctness is proven unconditionally, and a variant of it has running time roughly $O((\log n)^6)$. $\endgroup$ – Sasho Nikolov Jul 7 '16 at 21:21
21
$\begingroup$

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).

$\endgroup$
  • 8
    $\begingroup$ Should've probably posted as an answer, since you got upvoted. Not that I mind though, glad I helped $\endgroup$ – Yuriy S Jul 7 '16 at 12:39
  • 1
    $\begingroup$ I'm not familiar with the algorithms used by the maximal prime gap project; however I'd think that if you're searching for a prime gap $> k$, you wouldn't need to check the primality of each integer. Instead, if you're at the verified prime $p$, the next integer you check is not $p+2$, but instead $p+k$ (and if that's not prime, work your way backwards). If you verify that (say) $p+k-6$ is prime, you don't need to check the primality of the other integers in the range... $\endgroup$ – poncho Jul 7 '16 at 17:01
  • $\begingroup$ I wish someone know, just an order of magnitude, how many primes there are with less than 20 digits. this QA is remarkably unmathematical :) Everyone's just saying "there's a lot!" and "there's a hell of a lot!" Geesh! $\endgroup$ – Fattie Jul 7 '16 at 20:18
  • 1
    $\begingroup$ @JoeBlow: according to the prime number theorem, there are approximately $10^{20} / \log 10^{20} \approx 2,171,472,409,516,259,138$ primes in that range. While this is just an approximation (and the lower dozen digits are almost certainly wrong), this is certainly within an order of magnitude. $\endgroup$ – poncho Jul 7 '16 at 20:23
  • 2
    $\begingroup$ @poncho People also counted the exact number of primes below $10^{20}$, it is $2{,}220{,}819{,}602{,}560{,}918{,}840$, see this Wikipedia subsection. That number divided by your number is about $1.02$ according to that table. This fraction tends to $1$ by the prime number theorem. $\endgroup$ – Jeppe Stig Nielsen Jul 8 '16 at 8:59
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.