11
$\begingroup$

So recently, an absurdly large prime number was found, but a lot of prime numbers less than it are still not known. I am wondering up to where we know all the primes.

I put "currently publicly known" because there is a chance that some government agency has a longer list for crypto reasons or something like that.

|cite|improve this question
$\endgroup$
  • $\begingroup$ math.stackexchange.com/tags/prime-numbers/info $\endgroup$ – draks ... Mar 14 '13 at 8:16
  • $\begingroup$ Such a prime list would be utterly useless for crypto. $\endgroup$ – CodesInChaos Mar 14 '13 at 8:39
  • $\begingroup$ @CodesInChaos Why? $\endgroup$ – Alexander Gruber♦ Mar 14 '13 at 8:54
  • $\begingroup$ @AlexanderGruber I can't think of any use. If you want to use them for breaking RSA, that's hopeless. Even easily broken RSA512 has 256 bit primes, of which there are far more than can be calculated or stored. There are algorithms which use smaller primes, for example Poly1305 uses a 130 bit prime. But that prime isn't secret, and was chosen to be the largest prime smaller than 2^130. $\endgroup$ – CodesInChaos Mar 14 '13 at 9:00
  • $\begingroup$ Is there no research value in cryptography in looking at families of specific primes? $\endgroup$ – Alexander Gruber♦ Mar 14 '13 at 9:03
6
$\begingroup$

The most efficient known way (please correct me if I'm wrong) to generate a list of consecutive primes from $2$ to $n$ is the Sieve of Eratosthenes, which in an optimized implementation (at least relying on what's written in Wikipedia) requires $O(n)$ time and something like $O(n^{1/2+\epsilon})$ memory. Given current computing abilities, I'd guess your prime is somewhere between $2^{50}$ and $2^{60}$.

Edit to clarify: Asking for an exact answer is meaningless, because given a prime of that size, it's pretty fast to calculate the next one.

Edit 2 to answer your question with another question. What do you mean by "known"? Do you want them all to be written down in a physical list? By the prime number theorem, there are about $\frac n {\log n}$ primes up to $n$, so you'd need a pretty big piece of paper (or hard drive) to write down the primes up to $2^{60}$ :)

|cite|improve this answer
$\endgroup$
  • 5
    $\begingroup$ I think there are faster sieves, like the Sieve of Atkin. $\endgroup$ – Waleed Khan Mar 14 '13 at 11:28
  • $\begingroup$ Nice, didn't know that one. But it doesn't change my guess by much. (And you can't do better than $O(\frac {n}{\log n})$ anyway, by PNT.) $\endgroup$ – Yoni Rozenshein Mar 14 '13 at 11:36
  • $\begingroup$ For very large primes, I believe that probabilistic approaches are used to verify prime-ness. So I think that it may be possible that we can get faster the $ \mathcal{O}\left(\frac{n}{\log n}\right) $ bound at the expense of accuracy, which we can rectify by later verifying the prime with another computer. $\endgroup$ – Waleed Khan Mar 14 '13 at 11:41
  • 3
    $\begingroup$ Waleed, my claim is simply that if you want to print $k$ numbers, you can't do it faster than $O(k)$. $\endgroup$ – Yoni Rozenshein Mar 14 '13 at 14:45
  • $\begingroup$ So you are saying a better question would be how large a list of primes can you generate in a reasonable amount of time given current hardware and algorithms? $\endgroup$ – fhyve Mar 14 '13 at 18:25
1
$\begingroup$

I don't think you can pinpoint such a prime. If you had a candidate, it wouldn't be too hard to determine the next larger prime. There are just too many of them.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ That's exactly what I thought. Nonsensical question. $\endgroup$ – Jean-Claude Arbaut Mar 14 '13 at 12:46
  • $\begingroup$ Hmm, in earlier versions of my question I had the word "approximately". Don't know why I took it out. $\endgroup$ – fhyve Mar 14 '13 at 18:23

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.