中國餘數定理 | Chinese Remainder Theorem (CRT)

中國餘式定理

如果N為合數 ( N=n1× n2 × n3 × ... × nnN = n_1 \times \ n_2 \ \times \ n_3 \ \times\ ...\ \times \ n_n ),同個質數可以一起算 (ex: n1=p3n_1 = p^{3})

假設我只有 (a1,a2,a3...ana_1,a_2,a_3 ... a_n , n1,n2,n3...nnn_1,n_2,n_3 ... n_n ),想要計算出一個 A 符合 x A  mod Nx\equiv \ A\ \ mod \ N

x a1  mod n1x\equiv \ a_1\ \ mod \ n_1
x a2  mod n2x\equiv \ a_2\ \ mod \ n_2
x a3  mod n3x\equiv \ a_3\ \ mod \ n_3
..................
..............
x an  mod nnx\equiv \ a_n\ \ mod \ n_n

經以下操作

  1. Ni=NniN_i = \frac{N}{n_i}

  2. ti N1  mod nit_i \equiv \ N^{-1}\ \ mod \ n_i

  3. x=i=1n(ai×Ni×ti)+k×Nx = \sum_{i=1}^n{(a_i\times N_i\times t_i)} + k\times N

通常 xx 會小於 NN,因此 x = a

實例 :

  • x 2851  mod 7733x\equiv \ 2851\ \ mod \ 7733

    • x 2  mod 11x\equiv \ 2\ \ mod \ 11
    • x 1  mod 19x\equiv \ 1\ \ mod \ 19
    • x 2  mod 37x\equiv \ 2\ \ mod \ 37

ni=[11,19,37]n_i = [11, 19, 37]

Ni=Nni:N=[703,407,209]N_i = \frac{N}{n_i} : N=[703, 407, 209]

ti N1  mod ni : t=[10,12,17]t_i \equiv \ N^{-1}\ \ mod \ n_i \ :\ t=[10,12,17]

x=2×10×703+1×12×407+2×17×209+7733×kx = 2\times10\times703 + 1\times12\times407 + 2\times17\times209 + 7733\times k

x=26050+7733×kx = 26050 + 7733\times k

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import operator
from functools import reduce
from Crypto.Util.number import inverse

def solve_crt(remainders, modules):
"""
Solving Chinese Remainder Theorem
@modules and @remainders are lists.
"""
x = 0
N = reduce(operator.mul, modules)
for i, module in enumerate(modules):
if module == 1:
continue
Ni = N // module
b = inverse(Ni, module)
x += remainders[i] * Ni * b
return x % N