Re:Factoring may be easier than we think (2016)
by enedil on Sunday June 30, 2019 @07:10PM
(#20321169)
In short, no. There's a reason that General Number Sieve is only used for numbers bigger that 10^80 and Elliptic Curve Method (ECM) is used instead. If number is smaller, than you don't benefit from the better complexity. This invalidates your point, because it might happen that your hardware is fast enough to factor a number using ECM and not fast enough to do the same with GNFS. So practically speaking, you don't have any assurance that what you have is fast or slow. Of course, it might happen that you actually manage to factor some big numbers, in that case you have the empirical proof you sought.
[ Parent
| on HN ]
Re:Factoring may be easier than we think (2016)
by seppel on Monday July 01, 2019 @07:48PM
(#20330844)
I agree in principle. But I disagree that you cannot test GNFS on small numbers. You can do this, but you are right that you might have trouble to easily verify that it has a better asymtotic complexity than other algorithms.