# 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.