Euclidean Algorithms and Congruences
Chinese Remainder Theorem Algorithms
Reconstructing an integer from residues, Garner's incremental method, and CRT as a strategy for controlling coefficient growth.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0516
The Chinese remainder theorem is both a reconstruction tool and a computational strategy. As a strategy it is one of the two standard answers to coefficient explosion, the other being lattice reduction.
The statement
Given pairwise coprime moduli and a residue for each, there is a unique value modulo the product satisfying all the congruences simultaneously.
Two reconstruction methods
| Method | Approach | Best when |
|---|---|---|
| Direct (Lagrange-style) | Build each term with a precomputed idempotent, then sum | Moduli fixed, many reconstructions |
| Garner's algorithm | Incremental mixed-radix construction, one modulus at a time | Moduli discovered progressively; early termination possible |
Garner's incremental reconstruction
- Take residues in orderProcess moduli one at a time.
- Compute the correctionDifference between the target residue and the current partial value, times the inverse of the running product.
- AccumulateAdd the correction times the running product.
- Update the productMultiply the running product by the new modulus.
The modular strategy
Many computations produce a result far smaller than their intermediate values. Working modulo several small primes and reconstructing avoids the intermediates entirely.
This is standard in polynomial GCD, determinant computation and linear system solving. See determinant computation and Hensel lifting, which is the prime-power analogue of the same idea.
Two things that can go wrong
Signed reconstruction
CRT naturally returns a representative in the range from zero to the product. When the true answer may be negative, map representatives above half the product to their negative counterparts — and ensure the bound accounts for this by using twice the expected magnitude.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.3.4. 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.