How big is RSA keyspace?

Nov 2013 – This entry has been corrected, to reflect that the probability that an integer “n” is prime, is proportional to 1 / ln(n.)

The probability that a randomly chosen 30 digit number will be prime, is proportional to 1 / ln(30.)

If you multiply that number by 10^30, you have an approximation of the raw bulk of prime numbers exactly 30 digits long.

RSA 1024 is near 310 digits, so the largest prime factor would be 155 digits long. The number of 155 digit keys alone would be proportional to 1 /  ln(155) * 10^155. To estimate all possible keys, it would be necessary to repeat that calculation for 154, 153 etc, and accumulate the summation.

Key selection algorithms vary, and each implementation may have its own method of ensuring well-chosen keys.

Apr 2014: Update.

By experimentation, I see that the cardinal number of primes “x” below some n, is greater than n/ln(n) for n < 2^31, but I speculate that the ratio of [n/ln(n)]/[x] goes to 1, as n goes to infinity. Upon consideration, it was premature of me to leap to the conclusion I could talk about RSA keyspace, from what I knew when I published.


About James Johnson

I am an amateur mathematician & political theorist who enjoys (occasionally cerebral) humor.
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s