12
$\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.

$\endgroup$
8
  • $\begingroup$ math.stackexchange.com/tags/prime-numbers/info $\endgroup$
    – draks ...
    Mar 14, 2013 at 8:16
  • $\begingroup$ Such a prime list would be utterly useless for crypto. $\endgroup$
    – CodesInChaos
    Mar 14, 2013 at 8:39
  • $\begingroup$ @CodesInChaos Why? $\endgroup$
    – Alexander Gruber ♦
    Mar 14, 2013 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, 2013 at 9:00
  • $\begingroup$ Is there no research value in cryptography in looking at families of specific primes? $\endgroup$
    – Alexander Gruber ♦
    Mar 14, 2013 at 9:03

2 Answers 2

Reset to default
8
$\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}$ :)

$\endgroup$
6
  • 5
    $\begingroup$ I think there are faster sieves, like the Sieve of Atkin. $\endgroup$
    – Waleed Khan
    Mar 14, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 18:25
2
$\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.

$\endgroup$
2
  • $\begingroup$ That's exactly what I thought. Nonsensical question. $\endgroup$
    – Jean-Claude Arbaut
    Mar 14, 2013 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, 2013 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.