How did they factor RSA 240?

The Yomster

4/5/24, 9:32 AM

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?

953

1 + 1

factoring

number-field-sieve

Maarten Bodewes

4/5/24, 10:14 AM

A bit of search turned up [the paper](https://eprint.iacr.org/2020/697.pdf) called "Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment"

Score:11

Crypto

Sam Jaques

4/5/24, 10:13 AM

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

+ 3

gnasher729

4/6/24, 11:02 AM

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.

gnasher729

4/6/24, 11:17 AM

Just checked: Your number of cycles is right. And the number of operations is probably higher.

Sam Jaques

4/6/24, 11:39 AM

Thanks, I think I used years for my calculation but wrote hours instead.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How did they factor RSA 240?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.