# How did they factor RSA 240?

Since NFS runs in essentially $$n^{1/3}$$ time, and RSA-240 is a composite of two 120-digit primes, shouldn't this have taken at least $$10^{40}$$ operations, not including any overhead? Even if you could do say $$10^{20}$$ ops / s as modern supercomputers can almost do, this still should have taken essentially $$\infty$$ years. So what is this massive speedup I'm missing?

• A bit of search turned up the paper called "Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment" Apr 5 at 10:14

## 1 Answer

$$\exp((\log n)^{1/3})\neq n^{1/3}$$.

If you work through the formula for $$L[\tfrac{1}{3},1.92]$$ and set the $$o(1)$$ term to $$0$$, you get $$2.4\cdot 10^{23}$$ operations for $$n\approx 10^{240}$$.

The reported computation was 900 core years on a 2.1 GHz CPU, which is about $$6\cdot 10^{19}$$ cycles, which is much closer. Bear in mind that asymptotic notation can hide factors that actually make the result smaller sometimes.

• I just looked at the linked document, and it says 1,000 core YEARS. Fifty top-of-the-range Macs for 4,000 dollars each can do this in a year for 200,000 dollars in total. Maybe 10,000 KWh. Apr 6 at 11:02
• Just checked: Your number of cycles is right. And the number of operations is probably higher. Apr 6 at 11:17
• Thanks, I think I used years for my calculation but wrote hours instead. Apr 6 at 11:39