# Why is it impractical to generate a semiprime dictionary? [duplicate]

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?

• Hint: based on this answer, compute how large your dictionary would need to be.
– fgrieu
Commented Jun 12, 2013 at 16:34
• The problem is that there more than $2^{1000}$ primes that fall into the range of RSA-2048. Totally infeasible to find them all. Commented Jun 12, 2013 at 17:29
• @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.)
– Reid
Commented Jun 12, 2013 at 18:25
• @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. Commented Jun 13, 2013 at 5:27
• That's okay. I'm sure a few external hard drives will be more than enough... perhaps not. Commented Jun 13, 2013 at 6:07