Chinese Remainder Theorem
- https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- https://qiita.com/masa0599/items/2c93189dcc6beee5d8c5
- https://cryptohack.org/courses/modular/crt1/
- https://www.youtube.com/watch?v=zIFehsBHB8o
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 n1, n2, … nk are defined, we can calculate x by the following approach.
# 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)