中国剩余定理

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

中国剩余定理（CRT)

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

定义

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

过程

1.计算所有模数的积 n；n=

2.对于第 i个方程:

​ a.计算;

​ b.计算在模意义下的逆元; 逆元

​ c.计算

3.方程组在模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等）的乘积

证明

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

当时，有

这是因为

所以

对于任意的的取值均符合

所以上述方法可行