中国剩余定理

发表于 更新于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 2 分钟

中国剩余定理（CRT)

在做题时遇到离散对数问题中碰到很多CRT相关知识，但最初了解比较浅显，现在准备再稍微细致的回顾一下。

定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中$n_1$ $n_2$ ······$n_k$ 两两互质)：

$$
\begin{cases} x\equiv a_1 \pmod{n_1}\\ x\equiv a_2 \pmod{n_2}\\ x\equiv a_3 \pmod{n_3}\\ ·····\\ ·····\\ ·····\\ x\equiv a_k \pmod{n_k} \end{cases}
$$

过程

1.计算所有模数的积 n；n=$n_1*n_2*···n_k$

2.对于第 i个方程:

​ a.计算$m_i=n/n_i$;

​ b.计算$m_i在模n_i意义下的逆元m_i^{-1}$; 逆元$m_im_i^{-1}\equiv 1\pmod{n_i}$

​ c.计算$c_i=m_im_i^{-1}$

3.方程组在模n意义下的唯一解为$x=\sum_{i=1}^{k}{a_ic_i}\pmod{n}$

代码

1
2
3
4
5
6
7
8
9
10
11
12

def CRT(k, a, r):
    n = 1
    ans = 0
    for i in range(1, k + 1):
        n = n * r[i]
    for i in range(1, k + 1):
        m = n // r[i]
        b =y=0
        exgcd(m, r[i], b, y)  # b * m mod r[i] = 1  exgcd是另一个用来求逆元的自定义函数未标
        ans = (ans + a[i] * m * b % n) % n
    return (ans % n + n) % n

当然了上述代码可能更多用于算法题中，密码学里python有很多强大的库可以直接调用CRT

1
2
3
4
from sympy.ntheory.modular import crt
a_list=[a1,a2,a3,····ak]
n_list=[n1,n2,n3,····nk]
x,n=crt(n_list,c_list)    //crt会返回一个元组（x,N）其中x就是我们所需要的通解，n就是所有模数（n1,n2等）的乘积

证明

虽然说密码学里直接秒了，但我还是觉得搞清背后逻辑会更有理解。

$当i\neq j时，有m_j\equiv 0 \pmod{n_i}$

$这是因为m_j=n/n_j$

$所以c_j \equiv 0 \pmod{n_i},c_i\equiv 1 \pmod{n_i} $

$ x \equiv \sum_{j=1}^{k}{a_jc_j} \equiv a_ic_i\equiv a_i\pmod{n_i}$

$对于任意的i的取值均符合x\equiv a_i \pmod{n_i}$

所以上述方法可行