# 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>" %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/chinese-remainder-theorem.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.