On generating all primes less than 2^x

re: generating all primes less than 2^x

Granted this would take a while, but the NSA has the time, the computers, and the other resources necessary to do this.

The basic fact of number theory here is the prime number theorem, which says that (for the purposes of this problem) the number of primes less than N approaches N/ln N. For N=2^192 (say, for cracking 384 bit PGP keys), that number is 2^192/133, which is about 2^185. The number of bits necessary to store all of these primes is even larger. A gigabyte is only 2^38 bits. In plainer language, there's just too many to store. This same calculation also explains why there will never be a shortage of primes. Eric