中國餘式定理

如果N為合數 ( $N = n_1 \times \ n_2 \ \times \ n_3 \ \times\ …\ \times \ n_n$ )，同個質數可以一起算 (ex: $n_1 = p^{3}$)

假設我只有 ($a_1,a_2,a_3 … a_n$ , $n_1,n_2,n_3 … n_n$ )，想要計算出一個 A 符合 $x\equiv \ A\ \ mod \ N$

$x\equiv \ a_1\ \ mod \ n_1$
$x\equiv \ a_2\ \ mod \ n_2$
$x\equiv \ a_3\ \ mod \ n_3$
$………$
$…….$
$x\equiv \ a_n\ \ mod \ n_n$

經以下操作

1. 令 $N_i = \frac{N}{n_i}$

2. 令 $t_i \equiv \ N^{-1}\ \ mod \ n_i$

3. 則 $x = \sum_{i=1}^n{(a_i\times N_i\times t_i)} + k\times N$

通常 $x$ 會小於 $N$，因此 x = a

實例 ：

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

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

令 $n_i = [11, 19, 37]$

令 $N_i = \frac{N}{n_i} : N=[703, 407, 209]$

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

則 $x = 2\times10\times703 + 1\times12\times407 + 2\times17\times209 + 7733\times k$

$x = 26050 + 7733\times k$

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