








  • $\begingroup$ Are these long scale or short scale billions? (Short scale, if I counted right.) $\endgroup$ – Paŭlo Ebermann Oct 23 '11 at 21:56
  • $\begingroup$ Short scale. Usually I try to use British English ("colour", "centre"...) but for numbers I follow American usage, so that our American friends do not misunderstand. $\endgroup$ – Thomas Pornin Oct 24 '11 at 0:48
  • 1
    $\begingroup$ Reading this answer again, the storage problem is even worse! According to the holographic principle, the maximum information density in a volume is proportional to the square of its radius (e.g., its surface area) rather than the cube (e.g., its volume). Redoing the math, we can only pack roughly $10^{84}$ values in the observable universe, and would need $10^{224}$ universes to store them. And of course, once you've stored them, you'd need to be able to efficiently look them up when needed, which is a whole other can of worms. $\endgroup$ – Stephen Touset Jan 5 '16 at 18:38
  • $\begingroup$ @ThomasPornin I am reading this again and appreciate your thinking and your level of sophistication. But let's try to push this a bit further. What if the storage problem was tackled in a different manner? What if, rather than storing each prime, the deity decided to store just enough sparse numbers, allowing it to jump to a number, and then walk from there up or down. How sparse would that data be? And lets say, given 5 years head start to create these sparse indexes, the actual search from any point to find the right private key, must not take more than 7 days. Would that make it feasible? $\endgroup$ – momo yesterday
  • $\begingroup$ The generating computer(s) would be able to generate randomly and keep only the found prime long enough from next, removing older ones. Or walk from zero + 2 to infinity, albeit that might put things into perspective. How long would it take to walk to 2^2048 ? $\endgroup$ – momo yesterday







  • $\begingroup$ Why are we counting atoms? An electron or proton is not an atom and much smaller... right? $\endgroup$ – momo Oct 24 '11 at 9:56
  • 4

You are underestimating something, either the number of primes that an attacker would have to generate and store, or the size of the primes that must be multiplied in standard factorisation-based cryptosystems. Current recommandations suggest taking $1024$-bit primes. The number of $1024$-bit primes is about $1.26\times 10^{305}$, according to this answer on math.stackexchange. Even if the attacker was able to generate a billion prime per second, it would not take a week to generate all such primes, it would take $4\times 10^{288}$ years, and I do not have good ways of describing how huge this number is. The number of particles in the universe is nothing compared to that. Even the cube of the number of particles in the universe is nothing compared to that. I'm not even talking about storing this gigantic list, or searching through it.

  • $\begingroup$ So, basically, the answer to the question "what stops an attacker" is: "reality". $\endgroup$ – Jörg W Mittag Feb 14 '17 at 1:54






The answer is no. It would not help at all to know all primes!

The proof is relatively simple from the fundamental theorem on the growth rate of primes. According to this theorem there are approximately $n/\log(n)$ primes less than $n$ for sufficiently large $n$. So if you are trying all divisors of $n$ less than $\sqrt{n}$, then you must try about $\sqrt{n}/\log(\sqrt{n})$ primes. This is about $\sqrt{n}/\log{n}$ primes as opposed to about $\sqrt{n}$ possible integers. As you see the speedup factor is $O(\log n)$ compared to brute force.

There are other methods of factorization that have much better asymptotic performance. The easiest one to understand is the modified Fermat's factorization which has an asymptotic performance $O(n^{1/3})$ [Lehman], in practice this can be reduced to $O(n^{1/4})$, although there is no well known proof for that. More advanced methods such as quadratic sieve or the general number field have much better asymptotic performance. These more advanced methods do not rely on knowing if a number is prime. So having a list of primes does not speed up these methods.


Your Answer

