> The post states that 800-bit claims would be 36 bits of work. I don't know what that means.

From the article: "Schnorr’s paper claims to factor ... 800-bit moduli in 8.4·10¹⁰ operations"

2^36 ~= 8.4·10¹⁰, so I guess "36 bits of work" means 2^36 operations. Analogous to how a password with 36 bits of entropy would require 2^36 guesses. My first time encountering the phrase "bits of work" as well, though.

It's in the abstract:

>Our accelerated strongprimal-dual reduction of [GN08] factors integers N≈2^400 and N≈2^800 by 4.2·10^9 and 8.4·10^10 arithmetic operations.

Increasing the length by a factor of 2^400 only increased the amount of work by a factor of 20? Staggering, if true in general.

Yeah, that's what got me. Doubling the length of the key only requires a single order of magnitude more work?. If that turns out to be true, I'm going to need to revise my beliefs about how the universe works. In particular, information theory and thermodynamics, because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. (Caveat: if the values of primes turn out to have a predictable pattern, that could provide the needed information. However, that would mean that the Riemann Hypothesis is false, and that'd be an even more astounding result.)

Thing is, RSA keys are rather 'sparse' because they are the product of two primes. There aren't that many primes, so there aren't that many numbers that only have two (proper) divisors.

Hence, if you look at the strength of the currently best-known attack on RSA keys, you see that the key strength grows quite slowly as the keys get larger. This is purely from how sparse prime numbers are. From [1] which quotes NIST in 2015 we see (both collumns are in bits):

    Strength  RSA modulus size
      80        1024
     112        2048
     128        3072
     192        7680
     256       15360

> Because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so.

Technically the information is still there, it was just thought to be very hard to extract. This paper shows an easier way to extract it.

[1] https://crypto.stackexchange.com/questions/8687/security-str...

Thanks very much.

Actually, you're only increasing the length of the number by a factor of 2, since 2^400 is a 400-bit number.

If true, it's still leaps and bounds ahead of anything we have today, though.

Fair point. "Increasing the key [not the length of the key] by a factor of 2^400".

2^36 "operations" can still take a lot of time if each operation is multiplying two giant numbers, unless the meaning of "operation" is somehow normalized to mean e.g. 64 bit integer operations.

> 2^36 "operations" can still take a lot of time if each operation is multiplying two giant number

It took me 3.3 years of actual computation time to do about 2^46 multiplication+modulo of two 2048 bit numbers on a Core i7. 2^36 of 2048 bit numbers should be doable in a day on an eight years old CPU.

P.S: that was on a single core, for the problem I solved was explicitly created as to not be parallelizable.

It didn't take long for custom ASICs for mining bitcoin to emerge. It wouldn't take long for custom ASICs to do these kinds of operations a lot faster than on a general purpose CPU to emerge.

Supposing the paper does describe a more efficient factorisation algorithm, that does not imply that factoring a 800 bit prime (like the author of this article suggests) would be cheap.

factoring a 800 bit prime is definitely cheap. ;-)

In fact, I'll do it right now for you for only one dollar per bit.