Re:We Cracked a 512-Bit DKIM Key for Less Than $8 in the Cloud
by jedwards1211 on Friday January 10, 2025 @12:57PM
(#42658019)
The wiki article on GNFS says:
> The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.
"Super-polynomial" means that the running time increases by more than the square.
In any case, even if the algorithm were just polynomial, the argument about squaring costs doesn't work out.
> The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.
"Super-polynomial" means that the running time increases by more than the square.
In any case, even if the algorithm were just polynomial, the argument about squaring costs doesn't work out.