> For the complete documentation index, see [llms.txt](https://www.ctfrecipes.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/chinese-remainder-theorem.md).

# Chinese Remainder Theorem

**The Chinese Remainder Theorem** (**CRT**) is a mathematical theorem that states that if we have a system of linear congruences (equations of the form "**`x ≡ a mod m`**") **with pairwise coprime moduli**, then there exists a unique solution for **`x`** modulo the product of the moduli.

The theorem is called "Chinese" because it was first stated by the ancient Chinese mathematician Sun Tzu Suan Ching.

The CRT is particularly useful in solving systems of simultaneous modular equations that are difficult or impossible to solve individually. For example, if we have two congruences:

$$
x \equiv 3 \bmod 4 \ x \equiv 2 \bmod 5
$$

It is not possible to find a single solution for **`x`** that satisfies both congruences.

However, using the CRT, we can find a unique solution for **`x`** that satisfies both congruences modulo the product of the moduli (`20`).

{% hint style="info" %}
The CRT has many applications in cryptography, number theory, and computer science. For example, it is used in RSA encryption to speed up the calculation of the modular inverse, and in constructing public-key cryptosystems based on integer factorization.
{% endhint %}

## Algorithm

In order to calculate a solution, two variables are needed :

$$
N = n\_1 \cdot n\_2 \cdot n\_3 \cdot ... \cdot n\_i \\\text{}\ E\_i = \left\[ \frac{N}{n\_1}, \frac{N}{n\_2}, \frac{N}{n\_3},...,\frac{N}{n\_i}\right]
$$

{% hint style="info" %}
The `Ei` values are composed multiplying all the n\_values each others except `n at position i`.
{% endhint %}

For each elements of `E` , the inverse (mod `ni`) `y` can be calculated using the [Fermat's Little theorem](/cryptography/general-knowledge/maths/modular-arithmetic/fermats-little-theorem.md#continuing-the-fermats-little-theorem) :

$$
E\_i \cdot y\_i = 1 \bmod n\_i
$$

Then a solution for x can be calculated using the following equation :

$$
x = a\_1 \cdot E\_1 \cdot y\_1 + a\_2 \cdot E\_2 \cdot y\_2 + a\_3 \cdot E\_3 \cdot y\_3 + ... + a\_i \cdot E\_i \cdot y\_i
$$

The unique solution is then `x % N`

## Python

```python
# remind, x = a mod n
# All the a values
a = [2,4,8]
# All the n values
n = [4,5,17]

N = 1

# Calcul N value
for i in n:
    N = N * i

# Compute E
E = [N // n[i] for i in range(len(n))]

# Get all y values
y = [pow(E[i],n[i]-2,n[i]) for i in range(len(n))]

# do the calcul x = ai * Ni * yi ... 
x = 0
for i in range(len(n)):
        x += a[i]*E[i]*y[i]
# Get the uniq solution
x %= N
print(x)
```

## Resources

{% embed url="<https://en.wikipedia.org/wiki/Chinese_remainder_theorem>" %}