2 ms·

For those who don’t get the joke: RSA-250 is named for the number of decimal digits (250 decimal digits, 829 bits), while RSA-2048 is named for the number of bi

For those who don’t get the joke: RSA-250 is named for the number of decimal digits (250 decimal digits, 829 bits), while RSA-2048 is named for the number of binary digits (617 decimal digits, 2048 bits), so we’re two-fifths of the way by length, not a tenth. On the other hand, given the complexity of current factorization algorithms, RSA-2048 is going to take something like 200 billion times more CPU power; of course, algorithmic and computational advances are likely to decrease that. The implications for RSA-1024 are more pressing: that’s only going to take about 200 times more CPU power.

bzxcvbn 5y ago
A tenth of the way in log scale is not much. There's a 1219 bits difference between RSA250 and RSA2048. And 2^1219 is around 10^367. We're not talking about 100 billion times more CPU time. We're talking about around a billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion times more.
- anderskaseorg 5y ago
  No. The relevant algorithm is not one that counts up from 2 to n and performs trial division. It’s the massively faster general number field sieve, whose complexity is approximately exp((64/9)^⅓ (ln n)^⅓ (ln ln n)^⅔), which is about 6.43897⋅10²³ for RSA-250 and 1.52374⋅10³⁵ for RSA-2048. https://en.wikipedia.org/wiki/General_number_field_sieve https://en.wikipedia.org/wiki/General_number_field_sieve