Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a fast GCD algorithm, an improvement on the simpler but slower Euclidean algorithm.
It is mainly used for big integers that have a representation as a string of digits relative to some chosen numeral system base, say β = 1000 or β = 232.
Lehmer noted that most of the quotients from each step of the division part of the standard algorithm are small.
[1]) Those small quotients can be identified from only a few leading digits.
Thus the algorithm starts by splitting off those leading digits and computing the sequence of quotients as long as it is correct.