4
$\begingroup$

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?

$\endgroup$
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, 2023 at 10:14

1 Answer 1

11
$\begingroup$

$\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.

$\endgroup$
3
  • $\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$
    – gnasher729
    Apr 6, 2023 at 11:02
  • $\begingroup$ Just checked: Your number of cycles is right. And the number of operations is probably higher. $\endgroup$
    – gnasher729
    Apr 6, 2023 at 11:17
  • $\begingroup$ Thanks, I think I used years for my calculation but wrote hours instead. $\endgroup$
    – Sam Jaques
    Apr 6, 2023 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.