The Chinese Remainder Theorem (CRT) is a mathematical theorem that provides a way to solve a system of linear congruences.

Specifically, it states that given a set of integers that are pairwise coprime and a set of remainders modulo those integers, there exists a unique solution, modulo the product of the integers, to the system of congruences.

The theorem has applications in number theory, cryptography, and computer science.

Theorem

Given m = m1·m2·...·mk, with (mi,mj) = 1 for all i ≠ j.

And a system of k equations:

x ≡ a1 (mod m1)
...
x ≡ ak (mod mk)

The system has a unique solution x ∈ Zm.

Existence Proof (by construction)

ci = m/mi · [(m/mi)^-1 mod mi], for i in 1..k

By hypothesis: mi | m and (m/mi,mi) = 1 → m/mi has multiplicative inverse modulo mi.

x = ∑ ai·ci, for i in 1...k

If i = j then ci mod mj = 1 else ci mod mj = 0. Follows that:

x mod m1 = a1·1 + a2·0 + ... + ak·0 = a1
x mod m2 = a1·0 + a2·1 + ... + ak·0 = a2
...
x mod mk = a1·0 + a2·0 + ... + ak·1 = ak

∎

Uniqueness Proof

Assume there are two solutions x1 and x2, then ∀ i in 1..k:

x1 mod mi = ai  → x  = mi·w + ai
x2 mod mi = ai  → x' = mi·k + ai
→ x1 - x2 = mi·(w - k) → mi|(x1 - x2)

Given that (mi,mj) = 1 and both mi|(x1 - x2) and mj|(x1 - x2) then (mi·mj)|(x1 - x2).

Follows that (m = m1·m2⋅...·mk)|(x1 - x2) and thus that x1 ≡ x2 (mod m)

∎

Note: is important when computing the solution x to don’t reduce m/mi modulo mi, just the inverse.

Arithmetic

Given that there is a unique solution, the transformation to vectored form is a bijection, and thus we are allowed to perform computations in the vectored form and then go back to the normalized form.

A value a ∈ Zm is first uniquely mapped into the smaller components:

a ↔ (a1, ... , ak) = (a mod m1, ... , a mod mk)

Then we can operate over the smaller components.

For example, if we want to multiply two values a and b in Zm:

a ↔ (a1, ..., ak) = (a mod m1, ..., a mod mk)
b ↔ (b1, ..., bk) = (b mod m1, ..., b mod mk)

We operate on the single components, and finally we map back to obtain a+b and a·b modulo m.

a+b ↔ (a1+b1, ..., ak+bk) = (a+b mod m1, ..., a+b mod mk)
a·b ↔ (a1·b1, ..., ak·bk) = (a·b mod m1, ..., a·b mod mk)

Note that the result holds because:

(a mod mi · b mod mi) mod mi = (a·b mod m) mod mi

And the uniqueness of the solution.

Doesn’t matter if we first reduce the result modulo m and then modulo mi, give that:

z = mq + r = m1·..·mk·q + r
→ (z mod m) mod mi = r mod mi
and also
→ z mod mi = r mod mi

In the end, via CRT we found the unique solution x = a+b ∈ Zn such that:

x mod mi = (a mod mi + b mod mi) mod mi

Example

m1 = 9, m2 = 10, m = 90

To vectored form:

a = 73 → (73 mod 9, 73 mod 10) = (1, 3)
b = 84 → (84 mod 9, 84 mod 10) = (3, 4)

a·b = x → (1⋅3 mod 9, 3⋅4 mod 10) = (3, 2)

Resolve the system:

x = 3 (mod 9)
x = 2 (mod 10)

Using the existence proof formula:

x = 3 · 90/9 · [(90/9)^-1 mod 9] + 2 · 90/10 · [(90/10)^-1 mod 10]
  = 3·10·1 + 2·9·9 = 192 = 12 (mod 90)

We found that a·b = 12 (mod 90)

Some Applications

RSA CRT Speed-up

The technique is applicable to RSA when we know the modulus prime factors p and q, thus it is generally applicable to the decryption and signing procedures.

If we have a number a ∈ Zn then we map it to (a mod p, a mod q).

We end up working with numbers having approximately half the digits of the original number.

Instead of performing one single exponentiation modulo n, we perform two exponentiation modulo p and q. For example, for digital signature if d is the secret exponent:

Sp = m^d mod p
Sq = m^d mod q

We then write the following system of two equations:

S ≡ Sp (mod p)
S ≡ Sq (mod q)

According to CRT the solution S to the system is unique and turns out to be the value we want to compute (i.e. m^d mod n).

Performance analysis

The cost of multiplying two numbers with k bits is ≈ k^2.

Because the exponent has k bits, the cost to perform m^d is approximately the cost of performing k iterations where each iteration has the cost of k^2 (let’s assume that we do a multiplication on each iteration). Thus, the total cost is ≈ k^3.

With CRT we execute two modular exponentiation m^d mod p and m^d moq q. Given that p and q have approximately k/2 bits the cost of each multiplication is ≈ (k/2)^2. The iterations for performing one exponentiation will thus cost ≈ (k/2)^3 = (k^3)/8. We are performing two exponentiation thus the total cost is ≈ (k^3)/4.

Using the CRT speedup can thus result in a significant reduction in the cost of performing modular exponentiation. Specifically, the cost is approximately 1/4 of the traditional method, resulting in a speed-up of around 75%.

Euler’s Totient Proof

Given two numbers m1 and m2 such that (m1,m2) = 1 and m = m1·m2, we want to prove that φ(m) = φ(m1)·φ(m2).

This is equivalent proving that there exist a bijection from Zm* to Zm1* × Zm2*.

f: Zm* → Zm1* × Zm2*

We define such function as:

f(x) = (x mod m1, x mod m2)

Starting from a number x ∈ Zm* then x mod mi is clearly in Zmi. But we require that x ∈ Zmi*.

Proof

Since x ∈ Zn*, by hypothesis we know that (x,m) = (x, m1·m2) = 1 and thus x doesn’t have any common factor with both m1 and m2.

For Euclidean algorithm 1 = (x,mi) = (mi, x mod mi) and thus x mod mi ∈ Zmi*.

Injectivity Proof

Let x1, x2 be two elements of Zm*.

If f(x1) = f(x2) = (a1, a2) then x1 and x2 are both solutions for the system:

    x ≡ a1 (mod m1)
    x ≡ a2 (mod m2)

For the CRT the solution x ∈ Zm* is unique, thus x1 = x2.

Surjectivity Proof

For each ai ∈ Zmi* for CRT there exist a unique solution x ∈ Zm.

Because (mi, ai = x mod mi) = 1 then for Euclidean algorithm (x, mi) = 1.

x doesn’t have any common factor with any mi and thus doesn’t have any common factor with m = m1⋅m2. Follows that x ∈ Zm*.

∎

Iterating the procedure this also proves that φ(∏ mi) = ∏ φ(mi) when the mis are pairwise coprime.