# 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