在上一章我们介绍了欧几里得算法和扩展欧几里得算法，这些算法在计算最大公约数和模逆元方面非常有用，但当我们需要处理多个模数时，效率可能会变得很低。中国剩余定理（Chinese Remainder Theorem，CRT）就是为了解决这个问题而诞生的。

这个定理也可以叫做孙子定理（Sunzi Theorem），是中国古代数学家孙子在《孙子算经》中提出的一个重要定理。原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”这个定理就是在这里提取的。👻

欢迎来到《密码学核心算法实战》的中国剩余定理CRT专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

中国剩余定理 😋

中国剩余定理的核心思想是：如果模数两两互质，那么一个同余方程组的解可以通过将各个模数对应的解进行组合来得到。具体来说，给定一组同余方程：

其中 $ m_1, m_2, \ldots, m_n $ 两两互质，则存在唯一的解 $ x $ 满足所有这些同余方程，且解在模 $ M = m_1 m_2 \cdots m_n $ 下唯一。

中国剩余定理的原理 🙃

设 $N = \prod_{i=1}^{m} n_i$。

构造

模数 $n_i$ 与 $n^*_i$ 互质，因此存在逆元 $t_i$ 使得

我们发现

用 $e_i$ 乘以 $a_i$，然后将它们相加，我们得到方程的一个解

因为 $x$ 里所包含的那些下标不等于 $i$ 的单项式因为 $e$ 的性质而在模 $n_i$ 下为 $0$，只留下下标等于 $i$ 的单项式 $a_i t_i n^_i$，而 $t_i n^_i \equiv 1 \mod n_i$，所以 $x \equiv a_i \mod n_i$。

中国剩余定理的算法操作 😚

中国剩余定理的算法操作主要包括以下步骤：

  1. 计算 $N = \prod_{i=1}^{m} n_i$。
  2. 对于每个 $i$，计算 $n^*_i = \frac{N}{n_i}$。
  3. 对于每个 $i$，计算 $t_i$，使得 $t_i n^*_i \equiv 1 \mod n_i$。
  4. 最后，计算 $x = \sum_{i=1}^{m} a_i t_i n^*_i \mod N$。
  5. 返回 $x$ 作为同余方程组的解。

中国剩余定理的实现 🤨

下面是中国剩余定理的一个简单实现：

def crt(a, n):
    # a 是同余方程组的余数列表，n 是模数列表
    N = 1
    for ni in n:
        N *= ni

    x = 0
    for ai, ni in zip(a, n):
        Ni = N // ni
        yi = pow(Ni, -1, ni)  # 计算 Ni 的逆元
        x += ai * yi * Ni

    return x % N

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

from sage.all import crt # sage环境中才生效
# a 是同余方程组的余数列表，n 是模数列表
x = crt(a, n) # 直接获得同余方程组的解
# 也可以将列表直接展开
x = crt([a1, a2, a3], [n1, n2, n3])

怎么样，是不是非常简单？🤣👉🤡

上一章：密码学算法 - 欧几里得算法 👈
下一章：密码学算法 - Tonelli-Shanks算法 👈
回到开始：关于我 👈

相关链接：
密码学数学基础 - 同余关系与模运算 👈