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?



complexity of greatest common divisor (gcd)
I cross-posted this question on [stackexchange](https://cstheory.stackexchange.com/questions/2708/complexity-of-greatest-common-divisor-gcd%20%22here%22) 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."


