Editing Euclidean algorithm (section)

=== Factorization algorithms ===
Calculating a greatest common divisor is an essential step in several [[integer factorization]] algorithms,<ref>{{harvnb|Crandall|Pomerance|2001}}, pp.  225–349</ref> such as [[Pollard's rho algorithm]],<ref>{{harvnb|Knuth|1997}}, pp. 369–371</ref> [[Shor's algorithm]],<ref>{{cite journal | author-link = Peter Shor|last=Shor |first=P. W. | year = 1997 | title = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer | journal = SIAM Journal on Scientific and Statistical Computing | volume = 26 |issue=5 | pages = 1484–1509 | doi=10.1137/s0097539795293172|arxiv=quant-ph/9508027 | bibcode = 1995quant.ph..8027S|s2cid=2337707 }}</ref> [[Dixon's factorization method]]<ref>{{cite journal | last = Dixon |first= J. D. | year = 1981 | title = Asymptotically fast factorization of integers | journal = Math. Comput. | volume = 36 | pages = 255–260 | doi = 10.2307/2007743 | jstor = 2007743 | issue = 153| doi-access = free }}</ref> and the [[Lenstra elliptic curve factorization]].<ref>{{cite journal | author-link = Hendrik Lenstra|last=Lenstra|first=H. W. Jr. | year = 1987 | title = Factoring integers with elliptic curves | journal = Annals of Mathematics | volume = 126 | pages = 649–673 | doi = 10.2307/1971363 | jstor = 1971363 | issue = 3| hdl = 1887/2140 | hdl-access = free }}</ref> The Euclidean algorithm may be used to find this GCD efficiently. [[Continued fraction factorization]] uses continued fractions, which are determined using Euclid's algorithm.<ref>{{harvnb|Knuth|1997}}, pp. 380–384</ref>