 Calculating a greatest common divisor is an essential step in several integer factorization algorithms, such as Pollard's rho algorithm, Shor's algorithm, Dixon's factorization method and the Lenstra elliptic curve factorization.The Euclidean algorithm may be used to find this GCD efficiently.Continued fraction factorization uses continued fractions, which are determined using Euclid's algorithm.