Let u and v be positive integers. We show that a slightly modified version of D. H. Lehmer’s greatest common divisor algorithm will compute gcd(u, v) (with u > v) using at most 0{(log u log v)/k + k log v + log u +k2} bit operations and 0(log и + k22k) space, where к is the number of bits in the multiprecision base of the algorithm. This is faster than Euclid’s algorithm by a factor that is roughly proportional to k.
Letting n be the number of bits in и and v, and setting к = [(log n)/4], we obtain a subquadratic running time of 0(n2/log n) in linear space.