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? Can it be proven not to lie in AC0? What are other complexity classes inside P that are of relevance here?
This is a major open question in complexity theory: it is not known if GCDs can be computed in NC, and it is not known if computing GCDs is P-complete.  The best parallel algorithms do have sub-linear parallel running time, one such algorithm being due to Sorenson:


  J. Sorenson.  Two fast GCD algorithms.  Journal of Algorithms, 1994.


If I am not mistaken, it is not even known if one can decide whether two integers are relatively prime in NC.