"Largest Known Prime Number Discovered; Has 17,425,170 Digits" http://www.sciencedaily.com/releases/2013/02/130213225424.htm

If we can find prime numbers larger than 17 milion digits, why can't we find all 1024bit (just 309 decimal digits) primes?

  • $\begingroup$ Generally when you see stuff about largest primes, it's all Mersenne Primes, which don't really have anything to do with general purpose primality testing. And neither has anything to do with cracking RSA. $\endgroup$ – Antimony Jun 24 '13 at 3:44
  • 18
    $\begingroup$ You are able to tell me a 100 digit number. So why can't you tell me all 9 digit numbers? $\endgroup$ – CodesInChaos Jun 24 '13 at 6:22

Due to the prime number theorem the number of primes with length $2^{1024}$ is approximately

$$\pi(2^{1024}) - \pi(2^{1023})\approx \frac{2^{1024}}{\ln(2^{1024})}- \frac{2^{1023}}{\ln(2^{1023})} \approx \frac{2^{{1024}}}{709.8} - \frac{2^{1023}}{709.1}\approx 2^{1013.5}$$

The number of atoms in the universe is approximately $10^{80} \approx 2^{265.75}$, which means...

Edit, fixing math:

... you would have to fit just around $2^{748} (\approx 2^{1013.5 - 265.75})$ prime numbers in every single atom in the universe in order to store this list.

To further break this down: Assume you could program atoms to output 1 prime at a time for 1 attosecond (shortest measured time, $2^{-18}s$), you would still need $2^{663.1}$ years, and it's been "only" $2^{33.7}$ years since the Big Bang.

Short: It's far, far beyond the anything ever achievable. And this is not due to our technical limitations, it's just not possible in existence.

  • $\begingroup$ How about subatomic particles from CERN? And dark matter?' It turns out that roughly 68% of the Universe is dark energy. Dark matter makes up about 27%. The rest - everything on Earth, everything ever observed with all of our instruments, all normal matter - adds up to less than 5% of the Universe. ' $\endgroup$ – user129789 Jun 24 '13 at 10:20
  • 7
    $\begingroup$ @user129789 Those numbers are so huge that no amount of optimization can make this approach feasible. Literally, you would need to store around $2^{750}$ primes into a single atom, which is an unimaginably large number, and for all intents and purposes infinite. Tylo, your calculation is wrong, by the way, that should be $2^{1013.5 - 265.75}$ (just about 744 orders of magnitude off :p) $\endgroup$ – Thomas Jun 24 '13 at 10:46
  • 1
    $\begingroup$ @user129789 If you find some way to store prime number information in dark matter, we can start recalculating. $\endgroup$ – Paŭlo Ebermann Jun 24 '13 at 11:25
  • 1
    $\begingroup$ Thanks Thomas, I corrected the math and added a tiny bit more. $\endgroup$ – tylo Jun 24 '13 at 12:31
  • 1
    $\begingroup$ That is because there are more efficient algorithms for factoring than trying out every possible prime as factor. But that was not the point in this question. $\endgroup$ – tylo Aug 30 '13 at 13:27

The Prime Number Theorem is a way to estimate the number of primes less than or equal to a given number. It basically says that for a given $x$, the number of primes $\le x$ is bounded by $$\frac{x}{\ln{x}}$$ For $2^{1024}$ this is a very large number. It's also worth noting that this would be essentially useless for cracking RSA because RSA moduli are semiprimes, not primes. They're products of two large prime numbers, so really you'd have to compute the products of all pairs of primes $\le x$, which is $$\frac{(2^{1024})(2^{1024} - 1)}{2}$$ Also a very large number.

Even if some crazy billionaire or the NSA did this, all you'd have to do is use 4096-bit keys. Public-key crypto would get a bit slower but generating all those numbers again would take exponentially more effort.

  • $\begingroup$ 'RSA moduli are pseudoprimes, not primes.' <-- so??? You still need to compute 2 2^1024 primes? $\endgroup$ – user129789 Jun 24 '13 at 1:36
  • $\begingroup$ @user129789 Even if we assumed that you could calculate all those $2^{1024}$ primes - never mind all their products pairwise, to make a huge lookup table - instantly (that is ludicrous but let us imagine). How much space would you need to store them all (1024 bits per prime)? $\endgroup$ – Thomas Jun 24 '13 at 1:44
  • 3
    $\begingroup$ This is a nonstandard use of the term "pseudoprime". The standard meaning is "a composite number that satisfies some relation that is true of all prime numbers, and false for most composites", the most common one being $2^{p-1} \equiv 1 \mod p$ $\endgroup$ – poncho Jun 24 '13 at 2:51
  • 1
    $\begingroup$ @poncho: the term I usually see is semiprime. $\endgroup$ – Reid Jun 24 '13 at 3:30
  • $\begingroup$ Ah yeah, sorry folks. I knew it was either pseudoprime or semiprime, and I chose the wrong one >.< Editing it now. $\endgroup$ – pg1989 Jun 24 '13 at 4:52

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