Upper limit?
Martin James Cochran
Martin.Cochran at Colorado.EDU
Sat Jul 5 13:56:38 EDT 2008
On Jul 4, 2008, at 9:46 PM, Allen wrote:
> Is there an upper limit on the number of RSA Public/Private 1024 bit
> key pairs possible? If so what is the relationship of the number of
> 1024 bit to the number of 2048 and 4096 bit key pairs?
Using the prime number theorem you can get an estimate on the number
of such pairs. Prime number theorem says that there are asyptotically
2^{512}/ln(2^{512}) primes less than 512 bits. So there are roughly
2^{512}/ln(2^{512}) - 2^{511}/ln(2^{511}) ~ 2^{511}/ln(2^{512} 512-bit
primes. Squaring this and dividing by two will give the approximate
number of pairs - 2^{1021}/(ln(2^{512}))^2.
Generalizing this for a n-bit RSA modulus gives 2^{n-3}/(ln(2^{n/
2}))^2 expected pairs.
Of course, well-chosen RSA primes usually have some special properties
so that (p-1) and (q-1) don't have too many small factors and so that
(p-q) isn't smaller than 2^{n/4}, so the above figures might be off by
a bit if you consider the resulting distribution. But they should
still be fairly close (maybe within a factor of ln(2^{n/2})?).
Martin
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list