Editing Binary GCD algorithm (section)

==Extensions==

The binary GCD algorithm can be extended in several ways, either to output additional information, deal with [[Arbitrary-precision arithmetic|arbitrarily large integers]] more efficiently, or to compute GCDs in domains other than the integers.

The ''extended binary GCD'' algorithm, analogous to the [[extended Euclidean algorithm]], fits in the first kind of extension, as it provides the [[Bézout coefficients]] in addition to the GCD: integers <math>a</math> and <math>b</math> such that <math>a\cdot{}u + b\cdot{}v = \gcd(u, v)</math>.<ref name="egcd-knuth"/><ref name="egcd-applied-crypto"/><ref name="egcd-cohen"/>

In the case of large integers, the best asymptotic complexity is <math>O(M(n) \log n)</math>, with <math>M(n)</math> the cost of <math>n</math>-bit multiplication; this is near-linear and vastly smaller than the binary GCD algorithm's <math>O(n^2)</math>, though concrete implementations only outperform older algorithms for numbers larger than about 64 kilobits (''i.e.'' greater than 8×10<sup>19265</sup>).  This is achieved by extending the binary GCD algorithm using ideas from the [[Schönhage–Strassen algorithm]] for fast integer multiplication.<ref name="stehlé-zimmermann"/> 

The binary GCD algorithm has also been extended to domains other than natural numbers, such as [[Gaussian integers]],<ref name="weilert"/> [[Eisenstein integers]],<ref name="eisenstein"/> quadratic rings,<ref name="some-quadratic-rings"/><ref name="UFD-quadratic-rings"/> and [[Ring of integers|integer rings]] of [[number fields]].<ref name="integer-rings" />