The Chinese Remainder Theorem: One Theorem Holding Up Half of Cryptography

This article has three layers:

1. The intuition: General Han Xin counts his soldiers
2. Real-world use: five places the CRT appears in cryptography
3. The mathematics: the ring isomorphism, a constructive proof, the polynomial version and a worked example

Layer 1: The Intuition

1.1 Han Xin counts his soldiers

A problem from the Sunzi Suanjing (around the 4th century):

There is an unknown number of things. Counted by threes, two remain; counted by fives, three remain; counted by sevens, two remain. How many things are there?

The answer is $23$. A popular story tells it as "Han Xin counting soldiers": have the soldiers line up in rows of three, five and seven, hear only how many are left over each time, and you can deduce the total (uniquely, below $105$).

1.2 One number, two "ID cards"

Each number from $0$ to $14$ is uniquely identified by the pair "remainder when divided by 3, remainder when divided by 5":

15 numbers, 15 different remainder pairs, in one-to-one correspondence. Better still: addition and multiplication can be done separately on each side. For example $4 \times 7 = 28 \equiv 13 \pmod{15}$; with remainder pairs:

$$(1, 4) \times (1, 2) = (1 \cdot 1 \bmod 3,\ 4 \cdot 2 \bmod 5) = (1, 3),$$

and the table shows that $(1, 3)$ is exactly $13$.

1.3 Why this is useful

The cost of big-number arithmetic grows quickly with size (multiplication costs roughly the square of the number of digits). Splitting a 2048-bit number into two 1024-bit remainders makes each side's multiplication 4 times cheaper, and the two sides can run in parallel. This is divide and conquer.

Layer 2: Real-World Use

In addition, the analysis of Carmichael numbers in "Where Primes Come From" and the Lagrange interpolation in "Shamir's Secret Sharing" follow the same idea (Lagrange interpolation is itself the CRT over a polynomial ring).

Layer 3: The Mathematics

3.1 The theorem

Let $m_1, \dots, m_k$ be pairwise coprime and $M = m_1 \cdots m_k$. Then the map

$$\pi: \mathbb{Z}_M \to \mathbb{Z}_{m_1} \times \cdots \times \mathbb{Z}_{m_k},\qquad x \mapsto (x \bmod m_1, \dots, x \bmod m_k)$$

is a ring isomorphism.

Proof sketch (the standard abstract algebra approach):

1. First consider $\tilde\pi: \mathbb{Z} \to \prod \mathbb{Z}_{m_i}$, which is clearly a ring homomorphism (each component is a reduction homomorphism);
2. Its kernel is "the numbers divisible by every $m_i$", which by pairwise coprimality is $M\mathbb{Z}$;
3. By the first isomorphism theorem, $\mathbb{Z}/M\mathbb{Z} \cong \operatorname{im}\tilde\pi$;
4. Both sides have $M$ elements, so injective means surjective, and it is an isomorphism.

A more general version: in a commutative ring $R$, pairwise coprime ideals $I_1, \dots, I_k$ (with $I_i + I_j = R$) satisfy $R / (I_1 \cdots I_k) \cong R/I_1 \times \cdots \times R/I_k$.

3.2 How to combine again (constructing the inverse)

Let $M_i = M / m_i$ and find $y_i = M_i^{-1} \bmod m_i$ (coprimality guarantees it exists; use the extended Euclidean algorithm). Then

$$x = \sum_{i} r_i \, M_i \, y_i \bmod M.$$

The reason: $e_i = M_i y_i$ is "$1$ modulo $m_i$ and $0$ modulo every other $m_j$", so it is the "unit vector" of the $i$-th component. This is exactly the same idea as the Lagrange basis polynomial $L_j(x)$ in "Shamir's Secret Sharing".

3.3 A worked example: Han Xin's soldiers

3.4 The polynomial version

Replace $\mathbb{Z}$ with $F[x]$ and coprime integers with coprime polynomials, and the theorem still holds. If $f(x) = \prod_i (x - \alpha_i)$ with the $\alpha_i$ pairwise distinct, then

$$F[x]/(f) \cong F \times F \times \cdots \times F,\qquad g(x) \mapsto \big(g(\alpha_1), \dots, g(\alpha_n)\big).$$

Multiplication on the left is polynomial multiplication (convolution, slow); on the right it is pointwise (fast). This is the algebraic essence of the FFT / NTT: when the $\alpha_i$ are roots of unity, both directions can be done by divide and conquer in $O(n \log n)$.

Summary