Editing Greatest common divisor (section)

=== Complexity ===
The [[computational complexity]] of the computation of greatest common divisors has been widely studied.<ref>{{Cite book |first=Donald E. |last=Knuth | author-link = Donald Knuth |title=[[The Art of Computer Programming]] |volume=2: Seminumerical Algorithms |edition=3rd |year=1997 |publisher=Addison-Wesley Professional |isbn=0-201-89684-2}}</ref> If one uses the [[Euclidean algorithm]] and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most {{mvar|n}} [[bit]]s is {{math|''O''(''n''<sup>2</sup>)}}.{{cn|reason=This is far from obvious, imo.|date=March 2025}} This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication.

However, if a fast [[multiplication algorithm]] is used, one may modify the Euclidean algorithm for improving the complexity, but the computation of a greatest common divisor becomes slower than the multiplication. More precisely, if the multiplication of two integers of {{math|''n''}} bits takes a time of {{math|''T''(''n'')}}, then the fastest known algorithm for greatest common divisor has a complexity {{math|''O''(''T''(''n'') log ''n'')}}. This implies that the fastest known algorithm has a complexity of {{math|''O''(''n'' (log ''n'')<sup>2</sup>)}}.

Previous complexities are valid for the usual [[models of computation]], specifically [[multitape Turing machine]]s and [[random-access machine]]s.

The computation of the greatest common divisors  belongs thus to the class of problems solvable in [[quasilinear time]]. ''A fortiori'', the corresponding [[decision problem]] belongs to the class [[P (complexity)|P]] of problems solvable in polynomial time. The GCD problem is not known to be in [[NC (complexity)|NC]], and so there is no known way to [[parallel algorithm|parallelize]] it efficiently; nor is it known to be [[P-complete]], which would imply that it is unlikely to be possible to efficiently parallelize GCD computation. Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of [[integer linear programming]] with two variables; if either problem is in '''NC''' or is '''P-complete''', the other is as well.<ref>{{cite book |first1=D. |last1=Shallcross |first2=V. |last2=Pan |first3=Y. |last3=Lin-Kriz |chapter=The NC equivalence of planar integer linear programming and Euclidean GCD |title=34th IEEE Symp. Foundations of Computer Science |year=1993 |pages=557–564 |chapter-url=http://www.icsi.berkeley.edu/pubs/techreports/tr-92-041.pdf |archive-url=https://web.archive.org/web/20060905023143/http://www.icsi.berkeley.edu/pubs/techreports/tr-92-041.pdf |archive-date=2006-09-05 |url-status=live }}</ref> Since '''NC''' contains [[NL (complexity)|NL]], it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.

Although the problem is not known to be in '''NC''', parallel algorithms [[asymptotically faster algorithm|asymptotically faster]] than the Euclidean algorithm exist; the fastest known deterministic algorithm is by [[Benny Chor|Chor]] and [[Oded Goldreich|Goldreich]], which (in the [[CRCW-PRAM]] model) can solve the problem in {{math|''O''(''n''/log ''n'')}} time with {{math|''n''<sup>1+''ε''</sup>}} processors.<ref>{{cite journal |first1=B. |last1=Chor | author1-link = Benny Chor |first2=O. |last2=Goldreich |title=An improved parallel algorithm for integer GCD |journal=Algorithmica |volume=5 |issue=1–4 |pages=1–10 |year=1990 |doi=10.1007/BF01840374 |s2cid=17699330 }}</ref> [[Randomized algorithm]]s can solve the problem in {{math|''O''((log ''n'')<sup>2</sup>)}} time on <math>\exp\left(O\left(\sqrt{n \log n}\right)\right)</math> processors {{clarify|reason=with O notation in exponent, the complexity is not changed if the sqrt and the log are omitted|date=April 2018}} (this is [[superpolynomial]]).<ref>{{cite conference |first1=L. M. |last1=Adleman |first2=K. |last2=Kompella |chapter=Using smoothness to achieve parallelism |title=20th Annual ACM Symposium on Theory of Computing |pages=528–538 |year=1988 |isbn=0-89791-264-0 |location=New York |doi=10.1145/62212.62264 |s2cid=9118047 }}</ref>