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?
1
-
1$\begingroup$ A bit of search turned up the paper called "Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment" $\endgroup$– Maarten Bodewes ♦Apr 5 at 10:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
$\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.
-
$\begingroup$ 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. $\endgroup$ Apr 6 at 11:02
-
$\begingroup$ Just checked: Your number of cycles is right. And the number of operations is probably higher. $\endgroup$ Apr 6 at 11:17
-
$\begingroup$ Thanks, I think I used years for my calculation but wrote hours instead. $\endgroup$ Apr 6 at 11:39