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