Chinese Remainder Theorem Algorithms

Executive summary

Divide the problem across small moduli, then reassemble

Given pairwise coprime moduli, a system of congruences has a unique solution modulo their product. Constructively this converts one hard computation over large integers into many easy computations over small ones. The strategy — reduce, compute in parallel, reconstruct — is the standard defence against intermediate coefficient explosion in exact linear algebra, polynomial GCD and determinant computation.

Learning objectives

State the Chinese remainder theorem and its uniqueness condition.
Implement Garner's incremental reconstruction and explain its advantage.
Estimate how many primes are needed for a given result bound.
Recognise unlucky primes and handle them correctly.

Section 01Statement and construction

Let m₁, …, m_k be pairwise coprime and M their product. For any residues r_i there is a unique x modulo M with x ≡ r_i (mod m_i) for all i.

x = ∑_i r_i M_i (M_i⁻¹ mod m_i) mod M, M_i = M/m_i

Coprimality is not optional

If the moduli share a factor the system may be inconsistent, and the direct formula silently produces nonsense because the required inverse does not exist. Verify pairwise coprimality, or use distinct primes, which makes it automatic.

Section 02Garner's incremental algorithm

The direct formula requires the full product M in advance and does all its arithmetic at full width. Garner's algorithm instead builds the answer in mixed-radix form, performing each step in single precision and only widening at the end.

AlgorithmGarner's incremental CRTin: (r_i, m_i) → out: x mod ∏m_i

For i from 2 to k, precompute c_i ← (m₁·…·m_i−1)⁻¹ mod m_i. Depends only on the moduli, so it is reusable.
Set x ← r₁ and P ← m₁.
For i from 2 to k:
Set t ← (r_i − x) · c_i mod m_i. Single-precision arithmetic.
Set x ← x + t · P, then P ← P · m_i.
Return x, the unique solution modulo P.

The incremental property is the practical advantage: a modular determinant computation can keep adding primes until two successive reconstructions agree, without knowing the answer's size beforehand.

Section 03The multi-modular strategy

Stage 01Bound the resultDerive an a priori bound on the answer — Hadamard's bound for a determinant, Mignotte's bound for polynomial factors.
Stage 02Choose primesSelect enough primes, usually of machine-word size, so their product exceeds twice the bound. Word-size primes keep every operation single-precision.
Stage 03Compute in parallelSolve the problem independently modulo each prime. The subproblems are fully independent, so this parallelises perfectly.
Stage 04ReconstructApply CRT, then map into the symmetric range (−M/2, M/2] if the answer may be negative, or apply rational reconstruction if it may be a fraction.

Unlucky primes

A prime is unlucky if the structure of the problem degenerates modulo it — a matrix that is invertible over ℚ becoming singular, or a polynomial losing degree because its leading coefficient vanishes. Unlucky primes are rare but not negligible. Detect them by a rank or degree check and discard the prime; do not attempt to repair the result.

ReferenceFrequently asked questions

How many primes are needed?

Enough that their product exceeds twice the bound on the largest coefficient — the factor of two accommodates negative values represented in the symmetric range. With 63-bit primes, each contributes about 19 decimal digits of the final result.

Can I use the same primes every time?

For repeated computations of similar size, yes, and caching the Garner constants is worthwhile. But if an adversary or a structured input family can predict the primes, degenerate cases become more likely, so randomised selection from a pool is safer for library code.

Is the residue number system worth using for general arithmetic?

Rarely. Addition and multiplication are trivially parallel in RNS, but comparison, division and sign detection are all awkward and expensive. RNS suits fixed pipelines of additions and multiplications, not general-purpose arithmetic.

NavigateContinue in this stream

Curated next steps from this page. The site also surfaces algorithmically related reading below.

ProvenanceSources and further reading

This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.