From: hughes@ah.com (Eric Hughes)
Date: Sat, 27 Nov 93 20:34:45 PST
To: cypherpunks@toad.com
Subject: On generating all primes less than 2^x
In-Reply-To: <9311262038.AA27804@anon.penet.fi>
Message-ID: <9311280426.AA03899@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


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