CRT

CRT(中国剩余定理)

一、引入

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？

即求满足以下条件的整数：除以 3 余 2，除以 5 余 3，除以 7 余 2．

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知．

2 ×70 +3 ×21 +2 ×15 =233 =2 ×105 +23，故答案为 23．

为何呢：

$$70≡1(mod3)70≡1(mod3)， 21≡1(mod5)21≡1(mod5), 15≡1(mod7)15≡1(mod7), 105=3×5×7（模数的乘积）$$

二、定义

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

$$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \quad \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$$

三、过程

$$\begin{aligned} &\text{计算所有模数的积：} \\ &n = \prod_{i=1}^k n_i = n_1 \times n_2 \times \cdots \times n_k \\ \\ &\text{对于第 } i \text{ 个方程：} \\ &m_i = \frac{n}{n_i} \\ \\ &\text{计算 } m_i \text{ 在模 } n_i \text{ 意义下的逆元 } m_i^{-1}：\\ &m_i \cdot m_i^{-1} \equiv 1 \pmod{n_i} \\ \\ &\text{计算 } c_i = m_i m_i^{-1} \text{（不要对 } n_i \text{ 取模）：} \\ &c_i = m_i \cdot m_i^{-1} \\ \\ &\text{方程组在模 } n \text{ 意义下的唯一解为：} \\ &x = \sum_{i=1}^k a_i c_i \pmod{n} \end{aligned}$$

def CRT(k, a, r):
    n = 1
    ans = 0
    for i in range(1, k + 1):
        n = n * r[i]          # 计算所有模数的乘积 n = r1×r2×...×rk
    
    for i in range(1, k + 1):
        m = n // r[i]          # 除去当前模数的乘积 Mi = n/ri
        b = y = 0
        exgcd(m, r[i], b, y)   # 扩展欧几里得求 Mi 模 ri 的逆元 b
        # 满足: b × m ≡ 1 (mod r[i])
        
        ans = (ans + a[i] * m * b % n) % n   # 累加: ans += ai × Mi × inv(Mi)
    
    return (ans % n + n) % n   # 确保结果为正

四、在RSA中的简单应用

$$\begin{aligned} &\textbf{步骤 1：计算模 } p \text{ 下的明文分量} \\ &m_p = c^{d_p} \pmod{p} \\[2ex] &\textbf{步骤 2：计算模 } q \text{ 下的明文分量} \\ &m_q = c^{d_q} \pmod{q} \\[2ex] &\textbf{步骤 3：计算 } q \text{ 模 } p \text{ 的逆元} \\ &q \times q_{\text{inv}} \equiv 1 \pmod{p} \\[2ex] &\textbf{步骤 4：计算组合参数 } h \\ &h = (q_{\text{inv}} \times (m_p - m_q)) \bmod p \\[2ex] &\textbf{步骤 5：计算最终明文 } m \\ &m = m_q + h \times q \pmod{n} \end{aligned}$$