# Chinese Remainder Theorem

Last modified: 2023-09-02

Cryptography
Math

## Basic

If moduli (** n1, n2, etc.**) are co-primes, the following rules hold:

```
x ≡ a1 mod n1 # means `x % n1 = a1`
x ≡ a2 mod n2 # means `x % n2 = a2`
...
x ≡ ak mod nk # means `x % nk = ak`
```

In addition, if the values of ** a1, a2, … ak** and

**are defined, we can calculate**

`n1`

, `n2`

, … `nk`

**by the following approach.**

`x`

```
# Calculate N
N = n1 * n2 * n3 * ... * nk
# Calculate Ni (N1, N2, ..., Nk)
N1 = n2 * n3 * n4 ... * nk
N2 = n1 * n3 * n4 ... * nk
N3 = n1 * n2 * n4 ... * nk
...
Nk = n1 * n2 * n3 ... * n(k-1)
# Calculate xi (x1, x2, ..., xk)
N1*x1 ≡ 1 (mod n1) # means `N1*x1 % n1 = 1`
N2*x2 ≡ 1 (mod n2) # means `N2*x2 % n2 = 1`
N3*x3 ≡ 1 (mod n3) # means `N3*x3 % n3 = 1`
...
Nk*xk ≡ 1 (mod nk) # means `Nk*xk % nk = 1`
# x is sum of each ai*Ni*xi (mod N)
x = a1*N1*x1 + a2*N2*x2 + a3*N3*x3 + ... + ak*Nk*xk (mod N)
```

## Using crt method in Sympy

```
from sympy.ntheory.modular import crt
m = [7, 15]
a = [5, 12]
(x, y) = crt(m, a)
# x = 68, y = 77
```