vault

Chinese Remainder Theorem

24 min read

Chinese Remainder Theorem

Given pairwise-coprime moduli m_1, m_2, …, m_k and arbitrary residues a_1, a_2, …, a_k, the Chinese Remainder Theorem (CRT) asserts that the system of simultaneous congruences x ≡ a_i (mod m_i) for all i has a unique solution modulo M = m_1 · m_2 · … · m_k. The theorem dates to Sun Tzu’s Mathematical Manual (Sunzi Suanjing, 3rd–5th century CE), which posed the problem “There are certain things whose number is unknown. When divided by 3, the remainder is 2; by 5, the remainder is 3; by 7, the remainder is 2. What is the number?” — answer: 23, which we will derive in §2. The constructive proof gives an explicit formula x = Σ a_i · M_i · y_i (mod M), where M_i = M / m_i and y_i = M_i⁻¹ (mod m_i) is computed via the extended Euclidean algorithm or by Fermat for prime moduli (see Modular Inverse). CRT is the algebraic backbone of: RSA-CRT decryption (a 4× speedup over plain modular exponentiation, by computing mod p and mod q separately and combining), Garner’s formula for representing a single large integer as a residue tuple — the basis of residue number systems used in parallel arithmetic and high-radix hardware multipliers — and error-correcting codes like Reed-Solomon (which is essentially CRT over polynomial rings). This note develops the theorem, traces both Sun Tzu’s classical example and a numeric example with prime moduli, walks through the constructive proof, presents the iterative pairwise-CRT algorithm and Garner’s incremental algorithm, and explores the rich set of applications.

1. Intuition — A Number Is Pinned Down by Its Residues

A natural number x ∈ [0, M) can be uniquely identified by the tuple of its remainders (x mod m_1, x mod m_2, …, x mod m_k), provided that M = m_1 · m_2 · … · m_k and the moduli m_i are pairwise coprime (no two share a common factor > 1). The intuition: each modulus partitions [0, M) into “tracks” (residue classes); the intersection of one track per modulus picks out exactly one integer in [0, M).

A small example. Take moduli {3, 5}, both prime, so M = 15. The integers in [0, 15) are uniquely identified by their pair (x mod 3, x mod 5):

x:     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
mod 3: 0  1  2  0  1  2  0  1  2  0  1  2  0  1  2
mod 5: 0  1  2  3  4  0  1  2  3  4  0  1  2  3  4

All 15 pairs (0,0), (0,1), …, (2,4) appear exactly once. So the map x → (x mod 3, x mod 5) is a bijection from [0, 15) → {0,1,2} × {0,1,2,3,4}. Given a tuple, you can recover x uniquely.

What if the moduli are not coprime? Take {4, 6} with M = 24. The map x → (x mod 4, x mod 6) cannot be a bijection because gcd(4, 6) = 2, so x mod 4 and x mod 6 always agree mod 2 — there are only 4 · 6 / 2 = 12 valid residue pairs, not all 24. Some pairs are unreachable, and others have multiple preimages. CRT requires coprime moduli to deliver uniqueness.

A clock analogy: imagine three clocks with m_1 = 7, m_2 = 11, m_3 = 13 ticks per cycle (all coprime). Every 7 · 11 · 13 = 1001 minutes, all three clocks return to the same alignment (e.g., all reading 0). At every other minute in the cycle, the triple (c_1, c_2, c_3) of clock readings is unique — so observing the readings tells you exactly which minute it is. CRT formalizes this: given the residues (a_1, a_2, a_3), the underlying minute is uniquely determined modulo 1001.

A second perspective from algebra: CRT says the ring isomorphism

ℤ/M ℤ ≅ (ℤ/m_1 ℤ) × (ℤ/m_2 ℤ) × … × (ℤ/m_k ℤ)

holds when the m_i are pairwise coprime. The map sends x to (x mod m_1, …, x mod m_k), and CRT gives the inverse. This is more than convenient — it lets us do arithmetic in parallel: to multiply two integers mod M, multiply each component, then re-assemble. Computer hardware exploits this in residue number systems (§9.4).

2. Tiny Worked Example — Sun Tzu’s Problem and a Modern Variant

2.1 Sun Tzu’s Problem (3rd-5th century CE)

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

The moduli {3, 5, 7} are pairwise coprime, so CRT applies. M = 3 · 5 · 7 = 105.

M_1 = M / 3 = 35. We need y_1 = 35⁻¹ (mod 3). 35 mod 3 = 2, so we need the inverse of 2 mod 3, which is 2 (since 2·2 = 4 ≡ 1 mod 3). So y_1 = 2.

M_2 = M / 5 = 21. 21 mod 5 = 1, so y_2 = 1⁻¹ mod 5 = 1.

M_3 = M / 7 = 15. 15 mod 7 = 1, so y_3 = 1⁻¹ mod 7 = 1.

The CRT formula:

x = a_1 · M_1 · y_1 + a_2 · M_2 · y_2 + a_3 · M_3 · y_3 (mod M)
  = 2 · 35 · 2 + 3 · 21 · 1 + 2 · 15 · 1
  = 140 + 63 + 30
  = 233
  = 233 mod 105
  = 23

So x = 23. Sun Tzu’s answer.

Verify: 23 mod 3 = 2. ✓ 23 mod 5 = 3. ✓ 23 mod 7 = 2. ✓

The general solutions are x = 23 + 105k for any k ∈ ℤ; the smallest non-negative is 23.

2.2 A Modern Example with Larger Primes

x ≡ 4 (mod 11)
x ≡ 7 (mod 13)
x ≡ 3 (mod 17)

M = 11 · 13 · 17 = 2431.

M_1 = M / 11 = 221. y_1 = 221⁻¹ (mod 11). 221 mod 11 = 221 - 20·11 = 221 - 220 = 1, so y_1 = 1.

M_2 = M / 13 = 187. 187 mod 13 = 187 - 14·13 = 187 - 182 = 5. We need 5⁻¹ mod 13. By Fermat, 5⁻¹ ≡ 5^(11) mod 13, or just trial: 5·8 = 40 = 3·13 + 1, so 5⁻¹ ≡ 8 (mod 13). So y_2 = 8.

M_3 = M / 17 = 143. 143 mod 17 = 143 - 8·17 = 143 - 136 = 7. We need 7⁻¹ mod 17. Trial: 7·5 = 35 = 2·17 + 1, so y_3 = 5.

x = 4 · 221 · 1 + 7 · 187 · 8 + 3 · 143 · 5
  = 884 + 10472 + 2145
  = 13501
  = 13501 mod 2431
  = 13501 - 5·2431 = 13501 - 12155 = 1346

So x = 1346. Verify: 1346 mod 11 = 1346 - 122·11 = 1346 - 1342 = 4. ✓ 1346 mod 13 = 1346 - 103·13 = 1346 - 1339 = 7. ✓ 1346 mod 17 = 1346 - 79·17 = 1346 - 1343 = 3. ✓

3. The Algorithm

3.1 Pseudocode — Direct Formula

crt(a, m):                              # a, m are arrays of length k
    M := product of all m_i
    x := 0
    for i in 0..k-1:
        M_i := M / m_i
        y_i := mod_inverse(M_i, m_i)    # via extended Euclidean
        x := (x + a_i · M_i · y_i) mod M
    return x

This is the direct constructive form, O(k) modular inverses plus the summation.

3.2 Pseudocode — Iterative Pairwise CRT (Most Common in Practice)

The above formula is conceptually clean but requires computing M_i = M / m_i for each i, which means repeated big-integer divisions. The iterative pairwise form merges one congruence at a time and is friendlier for incremental input:

crt_iterative(a, m):
    x := a_0
    M := m_0
    for i in 1..k-1:
        # Merge x ≡ a_i (mod m_i) into the current (x mod M)
        # Solution: find x' = x + M·t where t · M ≡ (a_i - x) (mod m_i)
        diff := (a_i - x) mod m_i
        M_inv := mod_inverse(M, m_i)
        t := (diff · M_inv) mod m_i
        x := x + M · t
        M := M · m_i
    return x mod M

At each step, we’re solving M · t ≡ a_i - x (mod m_i) for t. This is solvable iff gcd(M, m_i) | (a_i - x). If the m_i are pairwise coprime, gcd(M, m_i) = 1, and the inverse M⁻¹ mod m_i exists. This form generalizes to non-coprime moduli with appropriate consistency checks (§9.1).

3.3 Garner’s Algorithm — Incremental Mixed-Radix

Garner 1959 gives a different reconstruction that produces x in a mixed-radix representation:

x = c_0 + c_1 · m_0 + c_2 · m_0 · m_1 + … + c_(k-1) · (m_0 · … · m_(k-2))

where each c_i ∈ [0, m_i) is determined by the congruences. The advantage: each coefficient c_i is bounded by m_i, so the partial sums grow gracefully in size — no need to maintain the running product M at full precision until the end.

Garner’s pseudocode:

garner(a, m):
    c := array of length k
    c_0 := a_0
    for i in 1..k-1:
        c_i := a_i
        for j in 0..i-1:
            c_i := (c_i - c_j) · mod_inverse(m_j, m_i) mod m_i
    # Reassemble x
    x := c_(k-1)
    for j in k-2 down to 0:
        x := x · m_j + c_j
    return x

Garner is widely used in cryptographic implementations and arbitrary-precision libraries because the partial residues stay small until the final reassembly.

4. Python Implementation

from math import prod
from functools import reduce
 
 
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Iterative extended Euclidean: returns (g, s, t) with s*a + t*b = g = gcd(a,b)."""
    old_s, s = 1, 0
    old_t, t = 0, 1
    while b != 0:
        q = a // b
        a, b = b, a - q * b
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return (a, old_s, old_t)
 
 
def mod_inverse(a: int, m: int) -> int:
    """a⁻¹ mod m via extended Euclidean. Raises if gcd(a, m) > 1."""
    g, s, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {m}")
    return s % m
 
 
def crt_direct(a: list[int], m: list[int]) -> int:
    """Solve x ≡ a[i] (mod m[i]) via the direct formula. Moduli must be pairwise coprime.
 
    Returns x in [0, M) where M = prod(m).
    """
    M = prod(m)
    x = 0
    for ai, mi in zip(a, m):
        Mi = M // mi
        yi = mod_inverse(Mi, mi)
        x = (x + ai * Mi * yi) % M
    return x
 
 
def crt_iterative(a: list[int], m: list[int]) -> int:
    """Solve x ≡ a[i] (mod m[i]) by merging one congruence at a time.
 
    More memory-efficient than crt_direct for many moduli; same answer.
    Moduli must be pairwise coprime.
    """
    x, M = a[0] % m[0], m[0]
    for ai, mi in zip(a[1:], m[1:]):
        diff = (ai - x) % mi
        M_inv = mod_inverse(M, mi)
        t = (diff * M_inv) % mi
        x = x + M * t
        M = M * mi
    return x % M
 
 
def crt_general(a: list[int], m: list[int]) -> int | None:
    """CRT for possibly non-coprime moduli.
 
    Returns the unique solution mod lcm(m), or None if the system is inconsistent.
    """
    x, M = a[0] % m[0], m[0]
    for ai, mi in zip(a[1:], m[1:]):
        g, s, _ = extended_gcd(M, mi)
        diff = ai - x
        if diff % g != 0:
            return None  # inconsistent
        # General solution: x' = x + M · ( (diff/g) · s mod (mi/g) )
        lcm = M // g * mi
        t = (diff // g) * s % (mi // g)
        x = (x + M * t) % lcm
        M = lcm
    return x
 
 
def garner(a: list[int], m: list[int]) -> int:
    """Garner's algorithm: mixed-radix reconstruction."""
    k = len(a)
    c = list(a)
    for i in range(1, k):
        for j in range(i):
            c[i] = (c[i] - c[j]) * mod_inverse(m[j], m[i]) % m[i]
    # Reassemble
    x = c[-1]
    for j in range(k - 2, -1, -1):
        x = x * m[j] + c[j]
    return x
 
 
# Demonstrations
if __name__ == "__main__":
    # Sun Tzu's classical problem
    assert crt_direct([2, 3, 2], [3, 5, 7]) == 23
    assert crt_iterative([2, 3, 2], [3, 5, 7]) == 23
    assert garner([2, 3, 2], [3, 5, 7]) == 23
 
    # Larger example
    assert crt_direct([4, 7, 3], [11, 13, 17]) == 1346
    assert crt_iterative([4, 7, 3], [11, 13, 17]) == 1346
 
    # Inconsistent system (non-coprime, conflicting)
    # x ≡ 1 (mod 4), x ≡ 2 (mod 6) — gcd(4,6)=2, but 1 - 2 = -1 not divisible by 2
    assert crt_general([1, 2], [4, 6]) is None
 
    # Consistent non-coprime system
    # x ≡ 1 (mod 4), x ≡ 5 (mod 6) — both ≡ 1 (mod 2); answer x = 17 mod lcm(4,6)=12
    assert crt_general([1, 5], [4, 6]) == 17 % 12 or crt_general([1, 5], [4, 6]) == 5

For very large moduli (RSA-scale), the inversions and multiplications use Fast Exponentiation and Karatsuba/FFT multiplication under the hood. Python’s arbitrary-precision integers handle the big-integer arithmetic transparently.

5. Complexity

5.1 Time

For k congruences with moduli of bit length b each:

  • Direct formula: O(k · b² + k² · b) with schoolbook arithmetic. The k · b² is for k modular inverses; the k² · b is for the products a_i · M_i · y_i where each operand is up to k · b bits.
  • Iterative pairwise: O(k² · b²) overall — k iterations, each doing constant-size operations on a running product whose size grows to O(k · b).
  • Garner: O(k² · b²) for the inverse computations and reductions; the final reassembly is O(k² · b).

In practice, for k small (a handful of moduli, as in RSA-CRT) these are all roughly equivalent. For very large k, Garner’s algorithm has the smallest constant factor due to keeping each c_i bounded.

5.2 Space

O(k · b) to store the result x (which has O(k · b) bits). Garner uses O(k · b) peak (the array c plus the running modulus). The direct formula needs O(k · b) for the precomputed M_i table.

5.3 Cost Compared to Direct Modular Exponentiation

In RSA decryption, plain c^d mod n (with n of 2b bits) costs O((log d) · M(2b)) = O(2b · M(2b)) where M(·) is multiplication cost. RSA-CRT computes m_p = c^(d mod (p-1)) mod p and m_q = c^(d mod (q-1)) mod q separately (each operand is b bits, exponent is b bits), then combines via CRT. Total cost: O(2 · b · M(b)) + O(M(2b)) for the CRT combine. With Karatsuba M(2b) = 4 · M(b), the speedup is roughly (2b · 4M(b)) / (2 · b · M(b) + 4M(b)) ≈ 4×. The 4× factor is the famous “RSA-CRT speedup.”

6. Why It Works — Constructive Proof

We prove the theorem in the “existence and uniqueness” form, with the construction giving the algorithm.

6.1 Statement

Theorem (CRT). Let m_1, m_2, …, m_k be pairwise coprime positive integers, and let M = m_1 · m_2 · … · m_k. For any choice of residues a_1, a_2, …, a_k, there exists a unique x ∈ [0, M) satisfying

x ≡ a_i (mod m_i)   for all i ∈ {1, 2, …, k}

6.2 Existence (Construction)

For each i, define M_i = M / m_i. Since the m_i are pairwise coprime, gcd(M_i, m_i) = 1 (the prime factors of M_i are exactly those of the other m_j’s, none shared with m_i). So the modular inverse y_i = M_i⁻¹ (mod m_i) exists by the Modular Inverse existence theorem.

Define

x = Σ_{i=1}^k a_i · M_i · y_i (mod M)

Verify that x ≡ a_j (mod m_j) for each j:

For i ≠ j, M_i is a multiple of m_j (since M_i = M / m_i includes the factor m_j). So a_i · M_i · y_i ≡ 0 (mod m_j). The only term that survives modulo m_j is the i = j term:

x ≡ a_j · M_j · y_j (mod m_j)

By construction, M_j · y_j ≡ 1 (mod m_j). So x ≡ a_j · 1 = a_j (mod m_j). ✓ This holds for every j, so x solves the system.

6.3 Uniqueness

Suppose x and x' both satisfy the system. Then x ≡ x' (mod m_i) for every i, i.e., m_i | (x - x') for every i. Since the m_i are pairwise coprime, their LCM is M = m_1 · m_2 · … · m_k. So M | (x - x'). If both x, x' ∈ [0, M), then |x - x'| < M, and the only multiple of M with absolute value less than M is 0, so x = x'. Uniqueness in [0, M) is established.

6.4 The Ring-Theoretic Reformulation

The map φ: ℤ/M ℤ → (ℤ/m_1 ℤ) × … × (ℤ/m_k ℤ), x ↦ (x mod m_1, …, x mod m_k), is:

  • A homomorphism (it preserves +, ·).
  • Injective by uniqueness (kernel is trivial).
  • Surjective by existence (every tuple is hit).

So φ is a ring isomorphism. This is the “modern” form of CRT, and it generalizes to ideals in any commutative ring (Dedekind domains, polynomial rings, etc.).

7. The Generalization to Non-Coprime Moduli

When the moduli are not pairwise coprime, the system x ≡ a_i (mod m_i) may or may not have a solution.

Theorem (Generalized CRT). The system has a solution iff for every pair (i, j), a_i ≡ a_j (mod gcd(m_i, m_j)). When a solution exists, it is unique modulo lcm(m_1, m_2, …, m_k).

Sketch. Pairwise compatibility is necessary: if a_i ≢ a_j (mod gcd(m_i, m_j)), no single x can satisfy both congruences. The proof of sufficiency proceeds by induction, merging two congruences at a time and verifying compatibility. The iterative algorithm crt_general in §4 implements this with the consistency check.

In practice, problems requiring generalized CRT often arise from polynomial / matrix algebra; the algorithm above is the standard solution.

8. Diagram — How the Pieces Fit Together

flowchart TD
  A["Input: residues a_1, ..., a_k\nModuli m_1, ..., m_k (pairwise coprime)"] --> B["Compute M = m_1 · m_2 · ... · m_k"]
  B --> C["For each i:\n  M_i = M / m_i"]
  C --> D["For each i:\n  y_i = M_i⁻¹ (mod m_i) via Extended Euclidean"]
  D --> E["x = Σ a_i · M_i · y_i (mod M)"]
  E --> F["Output: unique x ∈ [0, M)\nx ≡ a_i (mod m_i) for all i"]

  subgraph Why
    G["Why M_i works:\nM_i is divisible by every m_j (j ≠ i),\nso a_i · M_i · y_i contributes 0 mod m_j"]
    H["Why y_i works:\nM_i · y_i ≡ 1 mod m_i,\nso a_i · M_i · y_i ≡ a_i mod m_i"]
  end

What this diagram shows. The constructive procedure of CRT. Given k residues against k pairwise-coprime moduli, we compute M (the product, the modulus of the answer), then the M_i = M/m_i (each is “one modulus removed”), then their inverses y_i mod the corresponding m_i. The final x is a sum where each term a_i · M_i · y_i is engineered to contribute a_i mod m_i and 0 mod every other m_j. The “Why” cluster makes explicit the structural reason: M_i is a multiple of all m_j for j ≠ i, so it kills off contributions to those moduli; y_i rescales the m_i contribution to exactly 1, so multiplying by a_i gives the right residue. The whole construction is linear in the a_i’s — a critical fact that makes CRT a linear isomorphism between ℤ/M ℤ and the product ring, enabling parallel arithmetic.

9. Use Cases

9.1 RSA-CRT Decryption — The 4× Speedup

Standard RSA decryption: m = c^d mod n, where n = p · q is the modulus (~2048 bits) and d is the private exponent (~2048 bits). With Fast Exponentiation, this is O(log d) · M(2048) bit operations ≈ thousands of 2048 × 2048 multiplications.

RSA-CRT (Quisquater & Couvreur 1982) computes m differently. The private key includes p, q, d_p = d mod (p-1), d_q = d mod (q-1), q_inv = q⁻¹ mod p. Then:

m_p := c^(d_p) mod p          (1024-bit modular exp, ~4× cheaper than 2048-bit)
m_q := c^(d_q) mod q
h   := q_inv · (m_p - m_q) mod p
m   := m_q + h · q

The result m is the original plaintext. Each modular exponentiation is on a 1024-bit modulus (1/2 the size). With Karatsuba, M(2b) ≈ 3 · M(b), so each is ~3× faster, two of them are 1.5×, plus the small CRT combine. Empirically the speedup is ~4× over plain c^d mod n.

This optimization is so universal that essentially every production RSA implementation (OpenSSL, Bouncy Castle, libsodium) uses RSA-CRT for private-key operations.

9.2 Garner’s Formula in Big-Number Arithmetic

To represent a single very-large integer x (say 4096 bits), encode it as residues (x mod p_1, x mod p_2, …) for several moderate-sized primes p_i whose product exceeds x. Arithmetic on x proceeds in parallel in each residue. Garner’s algorithm reconstructs x from the tuple at the end.

This is the basis of residue number system (RNS) arithmetic, used in:

  • High-throughput hardware multipliers (each modular arithmetic unit can run in parallel).
  • DSP filters for digital signal processing (RNS arithmetic is fast and cancels rounding errors in fixed-precision contexts).
  • Lattice-based homomorphic encryption (BFV, BGV, CKKS schemes use RNS to speed up large-integer arithmetic).

9.3 Polynomial CRT and Reed-Solomon Codes

CRT generalizes from ℤ to polynomial rings K[x] (where K is a field). Given pairwise coprime polynomials f_1(x), …, f_k(x) and residues r_1(x), …, r_k(x), there is a unique polynomial g(x) mod f_1 · f_2 · … · f_k with g(x) ≡ r_i(x) (mod f_i(x)).

In Reed-Solomon error correction, each codeword is a polynomial evaluated at distinct points; the CRT structure says the polynomial is uniquely determined by enough evaluations. Decoding amounts to inverting the CRT map after correcting error positions. Used in CDs, DVDs, QR codes, deep-space communication.

9.4 Parallel Modular Arithmetic

To compute a sum like Σ x_i mod M for very large M, factor M = p_1 · p_2 · … (the p_i chosen as small primes). Compute Σ x_i mod p_i in parallel for each p_i (each thread/core works on a small modulus). Combine via CRT at the end. Used in scientific computing for exact rational arithmetic and in cryptography (Number Theoretic Transform-based homomorphic encryption).

9.5 Detecting Computation Errors via CRT

Run the same computation modulo two independent large primes p_1, p_2. If the two results agree (under CRT-reconstructed lift), high confidence the computation was correct; if they disagree, a bit error or hardware fault occurred. Used in scientific computing where rare hardware errors matter.

9.6 Goldreich-Goldwasser-Halevi Lattice Cryptography (Older)

Some early lattice-based schemes used CRT for parameter generation. (Modern post-quantum schemes like Kyber and Dilithium use NTT — Number Theoretic Transform — which is essentially CRT over a polynomial ring with carefully chosen prime moduli.)

9.7 Computing Modular Inverses Faster (Bach’s Method)

For computing a⁻¹ mod n where n = p · q is a known factorization, use CRT: compute a⁻¹ mod p and a⁻¹ mod q (each via Fermat or extended Euclidean on the smaller modulus), then CRT-combine. Faster than direct extended Euclidean on n.

10. Pitfalls

10.1 Forgetting the Coprime Requirement

The basic CRT formula assumes pairwise coprime moduli. If you apply it to non-coprime moduli, the inverses y_i may not exist (the algorithm errors out) or, worse, produce a “solution” that doesn’t actually satisfy the system. Always verify pairwise coprimality, or use the generalized form (§7).

10.2 Inconsistent Generalized System

For non-coprime moduli, a solution may not exist. x ≡ 1 (mod 4), x ≡ 2 (mod 6): gcd(4, 6) = 2, 1 mod 2 = 1, 2 mod 2 = 0 — inconsistent (no solution). The generalized algorithm must check this and return failure (or raise). Don’t blindly compute and assume the result is meaningful.

10.3 Big Integer Multiplication Costs

For large k and moderate-sized m_i, the products M_i = M / m_i are large integers. Naive O(k²) division gives quadratic blowup. The iterative pairwise form keeps the running product manageable. For very large k, Newton’s iteration for big-integer division is the standard speedup.

10.4 Wrong Choice of M_i in Hand Computation

M_i = M / m_i, not M_i = m_i / M or similar. Easy to mis-write under time pressure on a whiteboard. The mnemonic: M_i is “all moduli except m_i.”

10.5 Negative Residues from (a_i - x) mod m_i

In C-family languages, (a_i - x) % m_i can be negative if a_i < x. Use the defensive ((a_i - x) % m_i + m_i) % m_i. Python’s % is already non-negative; no fix needed there. See Modular Arithmetic §6.

10.6 Sign of Inverse from Extended Euclidean

The inverse y_i = mod_inverse(M_i, m_i) may be returned as a negative integer (e.g., -2 instead of m_i - 2). Reduce to [0, m_i) before plugging into the formula: y_i %= m_i.

10.7 RSA-CRT Side-Channel: The “Bellcore Attack”

A famous attack on RSA-CRT: if the CRT computation has a fault during one branch (e.g., a transient hardware error in m_p calculation), the attacker can compute gcd(c - m, n) to recover one of the prime factors. Mitigation: verify the result by re-encrypting (m^e mod n should equal c) before publishing. Production crypto libraries do this.

10.8 Different Conventions in garner for Coefficient Ordering

Some textbooks define Garner’s mixed-radix expansion as x = c_0 + c_1 · m_1 + c_2 · m_1 · m_2 + …, others use m_0 instead. The choice affects the inversions used. Check a single test case before relying on a hand-derived form.

10.9 Forgetting That y_i Is mod m_i, Not mod M_i

The inverse y_i should satisfy M_i · y_i ≡ 1 (mod m_i) — note the modulus is m_i, not M_i. A common bug: computing M_i⁻¹ mod M_i (which is the trivial 0 or 1 for many M_i). Always invert mod the small modulus.

11. Common Interview Problems

ProblemLeetCode # / SourceConnection
Sun Tzu’s classical CRT problemwarm-upDirect formula
Find smallest x satisfying multiple residue constraintscompetitiveIterative pairwise CRT
RSA-CRT decryption implementationcrypto courseworkCombines two mod p and mod q exponents
Number of pairs (x, y) with constraints mod m_1 and mod m_2competitiveCRT to count via single modulus lcm(m_1, m_2)
Reed-Solomon decodingcoursework / interview at storage companiesPolynomial CRT
Restore lost data from parity trackscourseworkRAID-6 uses CRT-like reconstruction
Random number generator with multiple seedscompetitiveCombined LCGs via CRT
Detect computation errorsscientific computingRun mod two primes and compare
Modular factorial reconstruction (Wilson-like)competitiveCRT on prime power moduli
Solve x² ≡ a (mod n) for composite ncompetitive / cryptoTonelli-Shanks per prime + CRT to combine

12. Open Questions

  • What is the asymptotically fastest CRT reconstruction? With FFT-based multiplication, it can be done in O(M(N) · log N) where N = log M is the bit length of the result and M(·) is multiplication cost. This matches the cost of multiplication of N-bit integers up to a logarithm, which is essentially optimal.
  • Can CRT be effectively parallelized? Yes — once the M_i, y_i are precomputed, the contributions a_i · M_i · y_i mod M are independent and can be computed in parallel; the final sum is a parallel reduction. Linear speedup with thread count.
  • What is the analog of CRT for non-commutative algebraic structures? For rings with non-trivial center, partial analogs exist (Wedderburn decomposition for semisimple Artinian rings). The general “structure of representations” theorems are the right level of abstraction.

13. See Also

Graph View

Backlinks