Engineering/Mathematics/Algorithm engineering
Euclid's Algorithm and Modular Computation
One two-thousand-year-old algorithm computes greatest common divisors, modular inverses, Chinese remainder coefficients, rational reconstructions and Reed–Solomon error locators. Learning where the extended Euclidean algorithm is hiding is one of the highest-leverage moves in computational algebra.
- Core algorithm
- Computing
- Reused everywhere
- ≈17 min read
- Enables RSA key setup
01
Executive summary
The Euclidean algorithm replaces the pair (a,b) by (b, a mod b) until the second entry is zero; the surviving value is the gcd. The extended version carries a pair of coefficients along, so that at termination it also reports s,t with sa + tb = gcd(a,b).
That certificate is what makes the algorithm ubiquitous. Setting b = n and gcd = 1 gives a modular inverse. Running it on polynomials gives inverses in F[X]/(f), hence finite field arithmetic. Stopping it early, rather than running to completion, solves rational reconstruction and decodes Reed–Solomon codes.
Repeated remaindering; O(ℓ) steps by a Fibonacci-worst-case argument.
Carries the linear combination; same asymptotic cost.
gcd(a,n)=1 gives a^{-1} ≡ s (mod n).
Halting mid-run yields the best rational approximation with bounded numerator and denominator.
02
The basic algorithm and its analysis
Euclidean algorithm
- input: integers a, b ≥ 0
- while b ≠ 0: (a, b) ← (b, a mod b)
- return a
O(ℓ) iterations on ℓ-bit inputs, each a division costing O(ℓ) word operations — O(ℓ²) bit operations overall.
Lamé's theorem
The number of division steps for inputs a > b > 0 is at most logφ(√5·b) ≈ 4.785·log10 b + 1.67, where φ is the golden ratio, and this is attained exactly when a and b are consecutive Fibonacci numbers. The heuristic reason: each step reduces the pair by at least a factor of φ on average, and a run of small quotients is the worst case.
- Average behaviour is better than worst case. The average number of steps is about (12 ln 2/π2)·ln b ≈ 0.843·ln b, a result of Heilbronn and Dixon; quotients follow the Gauss–Kuzmin distribution, with quotient 1 occurring about 41% of the time.
- Binary gcd replaces division with subtraction and shifts. It performs more iterations but each is far cheaper on hardware without a fast divider, and it is often the practical winner for word-size and moderate operands.
- Subquadratic gcd exists — Schönhage's half-gcd runs in Õ(ℓ) — but crossover occurs only at tens of thousands of bits, well above cryptographic operand sizes.
03
The extended Euclidean algorithm
Extended Euclidean algorithm
- input: a, b ≥ 0
- (r₀, s₀, t₀) ← (a, 1, 0); (r₁, s₁, t₁) ← (b, 0, 1)
- while r₁ ≠ 0:
- q ← ⌊r₀ / r₁⌋
- (r₀, r₁) ← (r₁, r₀ − q·r₁)
- (s₀, s₁) ← (s₁, s₀ − q·s₁)
- (t₀, t₁) ← (t₁, t₀ − q·t₁)
- return (r₀, s₀, t₀) // r₀ = gcd(a,b) = s₀·a + t₀·b
Same O(ℓ²) as the basic version. The invariant s_i·a + t_i·b = r_i holds at every step, and the coefficients stay bounded: |s_i| ≤ b/(2·gcd) and |t_i| ≤ a/(2·gcd).
Modular inversion
Run the algorithm on (a, n). If the gcd is 1, then s·a + t·n = 1, so s ≡ a−1 (mod n) after reduction to [0,n). If the gcd exceeds 1, no inverse exists — and the gcd itself is a non-trivial factor of n, which some factoring algorithms deliberately provoke.
| Method | Cost | Constant time? | Use case |
|---|---|---|---|
| Extended Euclid | O(ℓ2) | No — branch pattern depends on inputs | General purpose, public data |
| Binary extended gcd | O(ℓ2), better constants | No, without care | Software without fast division |
| Fermat: ap−2 mod p | O(ℓ3) | Yes, with a fixed exponentiation ladder | Secret data in prime fields |
| Batch inversion (Montgomery's trick) | one inversion + 3(k−1) multiplications | Inherits from the single inversion | Inverting k elements at once, as in elliptic curve batch operations |
| Constant-time divstep | O(ℓ2), fixed iteration count | Yes by construction | Modern cryptographic libraries |
Montgomery's batch trick: compute running products, invert the total once, then walk backwards recovering each inverse with two multiplications.
Do not use plain extended Euclid on secret values
The iteration count and quotient sizes depend on the operands, which leaks timing information about a secret. Where an inverse of secret data is required, use a fixed-iteration algorithm — exponentiation by p−2, or a constant-time divstep variant with a proven iteration bound.
04
Chinese remaindering in practice
Given residues ai modulo pairwise coprime ni, reconstruction produces the unique x modulo n = ∏ ni. Two schemes are standard.
| Scheme | Formula | Cost | Best for |
|---|---|---|---|
| Gauss / direct | x = ∑ ai·(n/ni)·[(n/ni)−1 mod ni] | O(k) inverses, then full-size arithmetic | Fixed moduli reused many times — precompute the coefficients |
| Garner / incremental | mixed-radix, one modulus at a time | All arithmetic stays small until the final assembly | Streaming or memory-constrained settings |
| Divide and conquer | product tree plus remainder tree | Õ(ℓ) for many moduli | Hundreds or thousands of small moduli |
RSA private operation via CRT
- precompute: d_p = d mod (p−1), d_q = d mod (q−1), q_inv = q^{-1} mod p
- m_p ← c^{d_p} mod p
- m_q ← c^{d_q} mod q
- h ← q_inv·(m_p − m_q) mod p
- m ← m_q + h·q
- verify m^e ≡ c (mod n) before releasing // fault-attack countermeasure
Two exponentiations at half the bit length: roughly a fourfold speed-up under a cubic cost model. The verification step costs one cheap public-exponent operation and is not optional.
The Bellcore fault attack
If a hardware fault corrupts exactly one of the two half-exponentiations, then gcd(me − c, n) reveals a prime factor of n. A single faulty signature is enough. Verifying the result before release, or computing both halves twice and comparing, closes this. Any CRT-RSA implementation without such a check should be treated as broken.
05
Speeding up algorithms via modular computation
Exact computation over ℤ or ℚ suffers from intermediate expression swell: entries in a matrix elimination, or coefficients in a polynomial gcd, grow far beyond the size of the input and output. The remedy is to compute modulo several small primes and reconstruct.
Bound the output
Derive an a priori bound H on the size of the answer — Hadamard's bound for determinants, Mignotte's bound for polynomial factors, or a direct size estimate.
Choose enough small primes
Pick word-size primes with product exceeding 2H, avoiding any prime that divides a leading coefficient or otherwise degrades the problem.
Solve modulo each prime
Each subproblem uses single-word arithmetic and is independent of the others, so the stage parallelises perfectly.
Reconstruct by CRT
Combine the modular images into a residue modulo the product of the primes.
Recover the integer or rational
Interpret the residue as a signed integer, or apply rational reconstruction if the true answer is a fraction.
Verify
Check the reconstructed answer against the original problem; this converts a probabilistic method into a certified one at low cost.
| Problem | Naive approach | Modular approach |
|---|---|---|
| Determinant of an integer matrix | Fraction-free elimination with growing entries | Modular determinants plus CRT, using Hadamard's bound |
| Polynomial gcd over ℤ[X] | Coefficient explosion in the subresultant algorithm | gcd modulo several primes, CRT, then a divisibility check |
| Linear system over ℚ | Exact rational elimination | Solve modulo primes, then rational reconstruction |
| Big-integer convolution | Direct multiplication | Multiply modulo several primes and recombine |
This is the same principle as the CRT speed-up in RSA — replace one big computation by several small independent ones — applied to symbolic computation instead of cryptography.
06
Rational reconstruction
Rational reconstruction
Given z and modulus n, and bounds r*, t* > 0 with 2r*t* ≤ n, there is at most one pair (r,t) with |r| ≤ r*, 0 < t ≤ t*, gcd(t,n) = 1 and r ≡ zt (mod n). It is found by running the extended Euclidean algorithm on (n, z) and stopping at the first remainder below r*.
The algorithm is the ordinary extended gcd with a different stopping rule. Its intermediate values are exactly the convergents of the continued fraction expansion of z/n, which is why continued-fraction and Euclidean treatments of these problems coincide.
Exact rational answers
Recover a fraction from its image modulo n — the final step of multi-modular linear algebra over ℚ.
Reed–Solomon decoding
The error locator and evaluator polynomials are a rational reconstruction of the syndrome polynomial, with degree bounds replacing size bounds.
Wiener's attack on RSA
A small private exponent d < n1/4/3 is recovered by reconstructing k/d from e/n — a direct application, and the reason small private exponents are forbidden.
Sequence and recurrence recovery
The polynomial version reconstructs the minimal polynomial of a linearly generated sequence, powering Wiedemann's algorithm.
The unifying view
Run the extended Euclidean algorithm and stop early: the remainder r and multiplier t at that point form the best rational approximation subject to the size constraint. Everything in the four cards above is that one sentence, instantiated in a different ring with a different notion of size.
07
Quick reference and FAQ
| Quantity | Value |
|---|---|
| gcd, extended gcd | O(ℓ2) bit operations |
| Worst-case iteration count | ≈ 4.785·log10 b (consecutive Fibonacci inputs) |
| Average iteration count | ≈ 0.843·ln b |
| Bézout coefficient sizes | |s| ≤ b/(2g), |t| ≤ a/(2g) |
| Modular inverse | one extended gcd; fails only when gcd > 1 |
| CRT for k moduli | O(k2) small operations, or Õ(ℓ) with a product tree |
| Rational reconstruction condition | 2r*t* ≤ n guarantees uniqueness |
| RSA CRT speed-up | ≈ 4× for the private operation |
Does the Euclidean algorithm ever fail or loop?
Why does the extended version cost no more asymptotically?
When should the binary gcd be preferred?
Is rational reconstruction the same as continued fractions?
09
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 4.
- D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed., Addison-Wesley, 1997 — §4.5.2 and §4.5.3.
- D. Boneh, R. A. DeMillo and R. J. Lipton, 'On the importance of checking cryptographic protocols for faults', EUROCRYPT '97, LNCS 1233, 37–51.
- M. Wiener, 'Cryptanalysis of short RSA secret exponents', IEEE Trans. Inform. Theory 36 (1990) 553–558.
- D. J. Bernstein and B.-Y. Yang, 'Fast constant-time gcd computation and modular inversion', IACR TCHES 2019(3), 340–398.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: euclidean-algorithm-and-modular-computationReview cycle: annual