# complexity of greatest common divisor (gcd)

Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest complexity class this problem is contained in? Can you provide a reference?

In this question I am not primarily interested in asymptotic bounds on the running time, but rather in complexity classes. Is the problem in $AC$? In $AC^1$? Can it be proven not to lie in $AC^0$? What are other complexity classes inside $P$ that are of relevance here?

-
I don't know about the complexity classes, but I think this is the state of the art for gcd computation: ams.org/journals/mcom/2008-77-261/S0025-5718-07-02017-0/…. –  Hans Lundmark Nov 3 '10 at 19:42
(a) There is a related MO post (which does not answer your question): mathoverflow.net/questions/25055/… ; (b) This question would be seen by more complexity experts at cstheory.stackexchange.com . –  Joseph O'Rourke Nov 3 '10 at 21:03

I cross-posted this question on stackexchange and John Watrous posted an answer. The gist was that it is not known whether gcd is in NC or P-complete. See, e.g., "J. Sorenson. Two fast GCD algorithms. Journal of Algorithms, 1994."

-
@ged: Do you know why, informally, should one conjecture that gcd is specifically in NC? –  Łukasz Grabowski Nov 5 '10 at 17:26
@Lukasz: I guess the main reason is that NC is one of the most well-known subsets of P. Another reason may be the ongoing quest for parallel gcd algorithms. However, if you know a different subset of P that you think is a more likely candidate, please let me know! –  ged Nov 9 '10 at 10:39