I'm reading a paper in which it's used the fact that a gcd computation of two numbers $(a,n)$, can be done in $O(\log n)$ time, and $[1]$ is referenced for the result. I haven't found that specific method. I've read through modifications of the extended euclidean algorithm, and modular algorithms, but all of them have linear complexities, not logarithmic. Could anybody point me to an algorithm that can do it in logarithmic time? Also, I don't actually need to calculate the gcd, just to test whether $$1<(a,n)<n$$

$[1]$ von zur Gathen, Gerhard. Modern computer algebra

  • 1
    $\begingroup$ See this question and answer. $\endgroup$ – Brian M. Scott Apr 5 '15 at 18:38
  • $\begingroup$ @BrianM.Scott Thank you very much. $\endgroup$ – MyUserIsThis Apr 5 '15 at 19:04
  • $\begingroup$ You’re very welcome. $\endgroup$ – Brian M. Scott Apr 5 '15 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.