2 ms·
Assuming you mean factoring large number, specifically semi-primes with broadly similar sized factors and no assumed structure, the answer is still no. Taking
by ColinWright 7y ago
Assuming you mean factoring large number, specifically semi-primes with broadly similar sized factors and no assumed structure, the answer is still no. Taking N as the number being factored and C a candidate that might contain a factor, taking GCD(N,C) is not a significant part of the process. The large part of the process is usually finding C.
And the article isn't claiming that the GCD code here takes the same time regardless of the input, it's saying that for two inputs of the same size the time take is the same. Time as a function of the input size is still proportional to the number of bits in the input, it's just that the routine takes the same time regardless of how many of those bits are 0, regardless of the structure of the input numbers.
========
To others commenting here, the guidelines[0] say:
Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith.
[0] https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html