中国剩余定理(CRT)

中国剩余定理(Chinese Remainder Theorem,简称 CRT)是数论中的经典定理,描述当若干个模数两两互质时,由这些模数构成的一元线性同余方程组必定存在解,且解在所有模数乘积的意义下唯一。它还给出了通过各模数的逆元显式构造这个解的方法,是数论与密码学的重要基础。

概述

该定理源自中国古代数学著作对物不知数问题的研究,即一堆物品三个一数、五个一数、七个一数分别余若干,求物品总数。这类问题正是求解同余方程组。中国剩余定理不仅证明了解的存在唯一性,还揭示了整数在互质模数下可被拆分并独立处理的深刻结构。

核心原理

• 前提条件:各方程的模数两两互质,记它们的乘积为总模。
• 构造分量:对每个模数,取总模除以该模数得到部分积,再求这个部分积关于该模数的逆元。
• 合成解:把每个余数、对应部分积与其逆元相乘后全部相加,再对总模取余,即得唯一解。
• 推广:当模数不互质时,可用扩展中国剩余定理逐一合并方程,合并时须检验相容性,不满足则无解。

应用场景

中国剩余定理在 RSA 解密加速、大整数运算的分块并行、秘密共享方案、哈希与纠错编码、以及分布式系统的编号分配中都有应用。它使得对一个大模数的运算可拆成若干小模数上的独立运算再合并,从而提升效率或增强安全性。

常见问题

问:模数不互质时定理还成立吗?答:基本形式要求两两互质。模数不互质时需用扩展形式逐步合并方程,且只有当各方程在公共因子上相容时才有解,否则方程组无解。

问:CRT 为什么能加速 RSA 解密?答:把关于大模数的幂运算拆成关于两个质因子的两次小模数幂运算再合并,可将解密速度提升数倍,是实际 RSA 实现的常见优化。