3 ms·

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

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