Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That's not correct. Consider, for example, a processor that can handle 2^31 computations per second. 2^32 operations can be computed in 2 time units, whereas 2^64 operations will take 2^33 time units.

search_space(n: number_of_bits) = 2^n * k

so search_space(1024)/search_space(512)=2^512, not 2^2.

Asymptotics in GNFS are better[0], but only on the order of e^(cbrt(512 * 64/9)) times more work, not 2^2.

This would give an approximation of math.exp(math.cbrt(512 * 64/9))*$8 = $40 million for 1024 bits.

[0] https://en.wikipedia.org/wiki/General_number_field_sieve



Pretty sure the search cost of GNFS is (bits)^2, the search cost of brute force is 2^(bits), if it was 2^(bits) GNFS would be no better than brute force.

->but only on the order of e^(cbrt(512 * 64/9))

e^(log(n)) = n




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: