# Chinese Reminder Theorem

Created: 2017-10-02
Updated: 2017-10-02

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 `mi`s are pairwise coprime.