Euclidean Algorithms and Congruences
The Euclidean Algorithm: Classical and Binary Variants
The classical Euclidean algorithm, the binary variant that replaces division with shifts, and how to choose between them.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0513
The greatest common divisor is the single most frequently invoked operation in computational number theory. Two algorithms dominate, and they trade a small number of expensive steps against a large number of cheap ones.
The classical algorithm
Repeatedly replace the pair by the smaller element and the remainder of the division. The process terminates because the remainder strictly decreases.
The binary algorithm
Stein's variant eliminates division entirely, using only subtraction, comparison and shifts. It rests on three observations.
- If both are even, the GCD is twice the GCD of the halves.
- If one is even and the other odd, the factor of two cannot divide the GCD, so it may be discarded.
- If both are odd, their difference is even and smaller than the larger of the two.
Binary GCD
- Extract common twosRemove the largest power of two dividing both; remember it for the end.
- Make both oddShift out factors of two from each operand individually.
- Subtract and shiftReplace the larger by the difference, then shift out its factors of two.
- RepeatContinue until one operand is zero.
- RestoreShift the result left by the common power of two.
Choosing between them
| Criterion | Classical | Binary |
|---|---|---|
| Operations per step | One division | Subtraction and shifts |
| Number of steps | Fewer | More, roughly proportional to bits |
| Small operands | Competitive | Usually faster |
| Large operands | Better, division amortises | Subtraction count grows |
| Hardware without fast division | Poor | Strong |
Where GCD appears
The operation is ubiquitous: reducing fractions, testing coprimality, detecting factors in Pollard rho and ECM, computing polynomial content, and as the inner loop of Hermite normal form.
Frequently Asked Questions
Why is the Fibonacci case the worst case?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.3.1-1.3.2. 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.