<p>Somewhat late in the day but the following <a href="http://www.sciencedirect.com/science/article/pii/S0022000000917252">paper</a> 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$. </p>

CC BY-SA 3.0
2015-01-05T16:30:56.843Z
Also see: http://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard/8017#8017
SamiD
CC BY-SA 3.0
2015-01-05T16:24:32.963Z
2015-01-05T16:24:32.963Z
SamiD
<p><a href="http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci07.pdf" rel="nofollow">This</a> paper, published in 2007, says that integer GCD is in NC.</p>

<p>Edit: The assertion is probably false. Check the comments.</p>

CC BY-SA 3.0
2013-09-05T13:21:54.183Z
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 (http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf).
Emil Jeřábek
CC BY-SA 3.0
2013-09-05T22:05:06.323Z
Did not know that. Thanks for pointing it out.
Apoorv Gupta
CC BY-SA 3.0
2013-09-05T22:16:56.870Z
I don't think this kind of answers should be downvoted.
Alessandro Cosentino
CC BY-SA 3.0
2013-09-04T20:17:36.043Z
2013-09-05T22:04:08.240Z
2013-09-05T22:04:08.240Z
Apoorv Gupta
<p>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:</p>

<blockquote>
  <p>J. Sorenson.  <a href="http://dx.doi.org/10.1006/jagm.1994.1006">Two fast GCD algorithms</a>.  Journal of Algorithms, 1994.</p>
</blockquote>

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

CC BY-SA 2.5
2010-11-04T13:42:55.917Z
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.
Felix Breuer
CC BY-SA 2.5
2010-11-04T14:51:23.640Z
Testing if two integers are relatively prime is also open according to this reference: [Limits to parallel computation](http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/limits.pdf), page 231, problem B.5.7.
Robin Kothari
CC BY-SA 2.5
2010-11-04T15:20:56.087Z
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. http://linkinghub.elsevier.com/retrieve/pii/S0020019009003640.
Felix Breuer
CC BY-SA 2.5
2010-11-04T13:38:40.900Z
2010-11-04T15:19:02.280Z
2010-11-04T15:19:02.280Z
John Watrous
<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2013-05-15T06:56:49.203Z
@ZsbánAmbrus, your link is for this question :), have you linked to the question you wanted to link to?
Kaveh
CC BY-SA 3.0
2013-05-15T08:11:30.573Z
Corrected link: http://mathoverflow.net/questions/44684/complexity-of-greatest-common-divisor-gcd .  Thanks for the warning, Kaveh.
Zsbán Ambrus
CC BY-SA 2.5
2010-11-04T11:14:04.830Z
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?
Joe Fitzsimons
CC BY-SA 2.5
2010-11-04T12:12:39.210Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-04T12:50:02.050Z
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.
Felix Breuer
CC BY-SA 2.5
2010-11-05T04:23:30.277Z
Ah, I see. Sorry for the confusion.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-06T17:41:01.040Z
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?
Ross Snider
<cc.complexity-theory><reference-request><complexity-classes><nt.number-theory>
complexity of greatest common divisor (gcd)
Felix Breuer
# complexity of greatest common divisor (gcd)

(Asked by: username_0 on 2010-11-04)

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?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, nt.number-theory

> **Comments:**
> **username_3**: 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?  
> **username_4**: @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.  
> **username_0**: 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.  
> **username_3**: Ah, I see. Sorry for the confusion.  
> **username_5**: 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?  
> **username_1**: @ZsbánAmbrus, your link is for this question :), have you linked to the question you wanted to link to?  
> **username_2**: Corrected link: http://mathoverflow.net/questions/44684/complexity-of-greatest-common-divisor-gcd .  Thanks for the warning, username_1.  

---

## 3 answers

### Answer by username_10 on 2010-11-04. Score: 46 | Accepted answer

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](http://dx.doi.org/10.1006/jagm.1994.1006). 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.

> **Comments:**
> **username_0**: 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.  
> **username_11**: Testing if two integers are relatively prime is also open according to this reference: [Limits to parallel computation](http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/limits.pdf), page 231, problem B.5.7.  
> **username_0**: 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. http://linkinghub.elsevier.com/retrieve/pii/S0020019009003640.  

---

### Answer by username_6 on 2015-01-05. Score: 8

Somewhat late in the day but the following [paper](http://www.sciencedirect.com/science/article/pii/S0022000000917252) 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$.

> **Comments:**
> **username_6**: Also see: http://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard/8017#8017  

---

### Answer by username_7 on 2013-09-04. Score: 3

[This](http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci07.pdf) paper, published in 2007, says that integer GCD is in NC.

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

> **Comments:**
> **username_8**: 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 (http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf).  
> **username_7**: Did not know that. Thanks for pointing it out.  
> **username_9**: I don't think this kind of answers should be downvoted.  

---

