Lehmer's GCD algorithm
Lehmer's GCD algorithm, named after D. H. Lehmer, is a fast GCD algorithm for multiple-precision arithmetic, which improves on the simpler Euclidean algorithm by doing most operations using only the leading digits of the values. "Digit" here is not necessarily a decimal digit; the algorithm is often used with integers represented using a base β such as β = 1000 or β = 232.