This might be a very simple question. However, I am just learning the concept, so just excuse me.

I am wondering why there is not any attempt to generate all semiprime numbers? (as an dict. attack to RSA-xxx algorithms). Because as far as I can see, all one is to do is as following:

  1. get a database of prime numbers
  2. multiply each prime number with each one. (which will require O(n^2) space)
  3. save the product.
  4. Of course, you will not do this for all of the prime numbers:)

    You will do this to prime numbers which will fall to the domain of RSA's random prime generator. In other words, which will create a $x$-bit number for RSA-$x$ (2048 bit for RSA-2048, for example).

I am sure one of these steps is impractical. Can you tell which one?

  • 1
    $\begingroup$ Hint: based on this answer, compute how large your dictionary would need to be. $\endgroup$
    – fgrieu
    Commented Jun 12, 2013 at 16:34
  • 1
    $\begingroup$ The problem is that there more than $2^{1000}$ primes that fall into the range of RSA-2048. Totally infeasible to find them all. $\endgroup$ Commented Jun 12, 2013 at 17:29
  • $\begingroup$ @CodesInChaos: Oh, come on, that's only $2.743 \times 10^{279}$ yottabytes! (Just to store the semiprimes, that is. You'd need approximately double the space to store the factors too.) $\endgroup$
    – Reid
    Commented Jun 12, 2013 at 18:25
  • $\begingroup$ @Reid no, you would need to store $2^{1999}$ multiples of those primes, which is quite a bit more. For each of them you would want both factors. $\endgroup$ Commented Jun 13, 2013 at 5:27
  • $\begingroup$ That's okay. I'm sure a few external hard drives will be more than enough... perhaps not. $\endgroup$
    – Thomas
    Commented Jun 13, 2013 at 6:07


Browse other questions tagged or ask your own question.