# 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?

• Well, clearly it is in FP by the Euclidean algorithm, but I don't really understand the rest of the question. AC, P and AC0 are all classes of decision problems, where as computing the GCD is not a decision problem. Is there some decision form of this problem you are interested in (i.e. is x = gcd(y,z)?), since you mention these classes? Commented Nov 4, 2010 at 11:14
• @Joe: My interpretation is that the asker is interested in whether the language {(x,y,i) | the i-th bit of gcd(x,y) is 1} is in NC, AC0, etc., but a clarification by the asker would be useful. Commented Nov 4, 2010 at 12:12
• Yes, Tsuyoshi's phrasing of the decision problem is what I had in mind - sorry for the ambiguity. However, please do not focus on the complexity classes I suggested, as I simply do not know which complexity classes are of relevance here. I am curious about any nontrivial complexity class which is a subset of P (or FP, resp.) that contains gcd. Commented Nov 4, 2010 at 12:50
• I'm curious about the case of gaussian integers. Quick google searches show ways to adapt the normal euclidean algorithm, but none of them discuss the relationship between the natural numbers and gaussian integers. Does any gcd algorithm over the natural numbers give us an algorithm over the gaussian integers with the same complexity? (I don't have an application, this is pure curiosity.) Also, are there efficient randomized algorithms for computing GCD with lower expected running times? Commented Nov 6, 2010 at 17:41
• Corrected link: mathoverflow.net/questions/44684/… . Thanks for the warning, Kaveh. Commented May 15, 2013 at 8:11

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.

• Thank you, that is what I wanted to know! However, if somebody knows other nontrivial subsets of P that are known to contain gcd, please let me know. Commented Nov 4, 2010 at 13:42
• Testing if two integers are relatively prime is also open according to this reference: Limits to parallel computation, page 231, problem B.5.7. Commented Nov 4, 2010 at 14:51
• A very recent reference is: Sorenson, Jonathan P. “A randomized sublinear time parallel GCD algorithm for the EREW PRAM.” Information Processing Letters 110, no. 5 (February 2010): 198-201. linkinghub.elsevier.com/retrieve/pii/S0020019009003640. Commented Nov 4, 2010 at 15:20

Somewhat late in the day but the following paper by Allender, Saks, Shparlinski proves that (among other lower bounds) that GCD is not in $\mathsf{AC}^0$ or $\mathsf{AC}^0[p]$ for any prime $p$.

• Commented Jan 5, 2015 at 16:30

This paper, published in 2007, says that integer GCD is in NC.

Edit: The assertion is probably false. Check the comments.

• The paper was never published, it was only posted on the author’s website. Moreover, the author himself does not seem to believe his 2007 paper is correct, as he lists the problem as open in his later papers (cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf). Commented Sep 5, 2013 at 13:21
• Did not know that. Thanks for pointing it out. Commented Sep 5, 2013 at 22:05
• I don't think this kind of answers should be downvoted. Commented Sep 5, 2013 at 22:16