Euclidean Algorithms and Congruences
Lehmer's Accelerated GCD Computation
Lehmer's method: running many GCD steps on single-precision leading digits before touching the full multiprecision operands.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0514
Lehmer's observation is that the sequence of quotients in the Euclidean algorithm usually depends only on the leading digits of the operands. Many steps can therefore be simulated in single precision and applied to the full operands in one batch.
The idea
Take the leading limbs of both operands. Run the Euclidean algorithm on those single-precision values, accumulating the transformation as a two-by-two integer matrix, and stop as soon as the quotient computed from the leading digits might differ from the true quotient.
Lehmer's accelerated GCD
- ExtractTake the top limb of the larger operand and the corresponding limb of the smaller.
- SimulateRun Euclidean steps on the single-precision pair, updating the transformation matrix.
- GuardStop when the quotient from the leading digits is no longer provably correct — a bound test on the matrix entries.
- ApplyApply the accumulated matrix to the full operands with multiprecision arithmetic.
- RepeatContinue until the operands fit in single precision.
Why it wins
The guard condition
Relationship to other methods
| Method | Approach | Complexity |
|---|---|---|
| Classical | One division per step | O(n^2) bit operations |
| Binary | Shifts and subtractions | O(n^2), smaller constant |
| Lehmer | Batched single-precision simulation | O(n^2), much smaller constant |
| Half-GCD | Divide and conquer | O(M(n) log n) |
Lehmer's method does not improve the asymptotic exponent — it reduces the constant substantially, which is why it remains the workhorse in the range where most computation actually happens. The same batching idea extends to the extended algorithm; see the extended algorithm.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.3.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.