Hacker News new | ask | show | jobs
by fdej 4664 days ago
10^12 is how much more work you have to do (according to the complexity estimate for the GNFS), regardless of how you do that work. If your custom-built hardware is 10^12 times faster than a general-purpose CPU, you can factor a 2048-bit number on your hardware as fast as a 768-bit number on general-purpose CPUs, but it will still take 10^12 times more work than factoring a 768-bit number on the same hardware. And I've never heard of GPUs or FPGAs giving a speedup of more than perhaps 10^4 on any problem, which still leaves a factor 10^8.
1 comments

I think you're confusing complexity with difficulty. It may be 10^12 times more complex. But, if you're making your own FGPAs or chips and you can just use different word sizes or massively add more gates or processing cores. Or, even more specialized custom built super computers. The capabilities of what they're able to fabricate I think mitigate most of the protection provided by using 2048bit over 1024bit. It seems you need to be talking on the scale of at least 4096bit before the problem becomes intractable due to the limits of technology and the processing improvements that can be provided by custom hardware.

To put it in simple terms, doing operations with a 32bit numbers and a 64bit numbers have a calculable complexity gap. But, that gap means very different things in terms of difficulty on a 8bit microprocessor vrs a 32bit microprocessor vrs a 64bit microprocessor.