算法背景
中国剩余定理（Chinese Remainder Theorem, CRT）是中国古代数学的杰出成就，最早记载于《孙子算经》中的”物不知数”问题。该定理指出：若模数两两互质，则同余方程组有唯一解（在模数的乘积意义下）。
在现代计算机科学中，CRT是RSA解密加速、大数模运算优化、秘密共享方案、纠错码设计等领域的核心工具。
数学原理
给定同余方程组：
$$\begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \vdots \ x \equiv a_n \pmod{m_n} \end{cases}$$
其中 $m_1, m_2, \ldots, m_n$ 两两互质。设 $M = m_1 m_2 \cdots m_n$，$M_i = M / m_i$，则方程组的解为：
$$x = \sum_{i=1}^{n} a_i M_i M_i^{-1} \pmod{M}$$
其中 $M_i^{-1}$ 是 $M_i$ 在模 $m_i$ 下的乘法逆元。
Java实现：基础CRT求解
import java.math.BigInteger;
import java.util.Arrays;
public class ChineseRemainderTheorem {
/**
* 扩展欧几里得算法: 求 ax + by = gcd(a,b) 的解
* @return [gcd, x, y]
*/
public static long[] exGcd(long a, long b) {
if (b == 0) {
return new long[]{a, 1, 0};
}
long[] next = exGcd(b, a % b);
long gcd = next[0];
long x = next[2];
long y = next[1] - (a / b) * next[2];
return new long[]{gcd, x, y};
}
/**
* 求a在模m下的乘法逆元 (假设gcd(a,m)=1)
*/
public static long modInverse(long a, long m) {
long[] eg = exGcd(a, m);
long x = eg[1];
return (x % m + m) % m;
}
/**
* 中国剩余定理求解
* @param a 余数数组
* @param m 模数数组 (必须两两互质)
* @return 最小非负整数解
*/
public static long solveCRT(long[] a, long[] m) {
int n = a.length;
long M = 1;
for (long mi : m) {
M *= mi;
}
long result = 0;
for (int i = 0; i < n; i++) {
long Mi = M / m[i];
long inv = modInverse(Mi, m[i]);
result = (result + a[i] * Mi % M * inv % M) % M;
}
return (result % M + M) % M;
}
public static void main(String[] args) {
// 《孙子算经》原题:
// 今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
long[] a = {2, 3, 2}; // 余数
long[] m = {3, 5, 7}; // 模数
long x = solveCRT(a, m);
System.out.println("Answer: " + x); // 23
// 验证
System.out.println("23 % 3 = " + (23 % 3));
System.out.println("23 % 5 = " + (23 % 5));
System.out.println("23 % 7 = " + (23 % 7));
}
}
Java实现：大数版本与RSA应用
import java.math.BigInteger;
import java.util.Random;
public class CRTRSA {
/**
* 使用中国剩余定理加速RSA解密
* 标准解密: m = c^d mod n
* CRT加速: 分别计算 mod p 和 mod q，再合并
*/
public static BigInteger rsaDecryptCRT(BigInteger c, BigInteger d,
BigInteger p, BigInteger q) {
BigInteger n = p.multiply(q);
// 预计算 (通常存储在私钥中)
BigInteger dp = d.mod(p.subtract(BigInteger.ONE));
BigInteger dq = d.mod(q.subtract(BigInteger.ONE));
BigInteger qInv = q.modInverse(p);
// 分别模p和模q计算
BigInteger m1 = c.modPow(dp, p);
BigInteger m2 = c.modPow(dq, q);
// Garner公式合并
BigInteger h = qInv.multiply(m1.subtract(m2)).mod(p);
BigInteger m = m2.add(h.multiply(q));
return m;
}
/**
* 标准RSA解密 (用于对比性能)
*/
public static BigInteger rsaDecryptStandard(BigInteger c, BigInteger d, BigInteger n) {
return c.modPow(d, n);
}
/**
* 大数中国剩余定理 (模数可非互质，需逐个合并)
*/
public static BigInteger solveCRTBig(BigInteger[] remainders, BigInteger[] moduli) {
BigInteger x = remainders[0];
BigInteger m = moduli[0];
for (int i = 1; i < remainders.length; i++) {
// 合并两个同余式: x ≡ a1 (mod m1), x ≡ a2 (mod m2)
BigInteger a2 = remainders[i];
BigInteger m2 = moduli[i];
// 求 m 在模 m2 下的逆元
BigInteger inv = m.modInverse(m2);
BigInteger t = a2.subtract(x).multiply(inv).mod(m2);
x = x.add(m.multiply(t));
m = m.multiply(m2);
x = x.mod(m);
}
return x;
}
public static void main(String[] args) {
// 生成测试用的RSA参数
Random rand = new Random(42);
BigInteger p = new BigInteger("104729"); // 小素数用于演示
BigInteger q = new BigInteger("104743");
BigInteger n = p.multiply(q);
BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger e = new BigInteger("65537");
BigInteger d = e.modInverse(phi);
BigInteger message = new BigInteger("123456789");
BigInteger cipher = message.modPow(e, n);
// CRT解密
long startCRT = System.nanoTime();
BigInteger decryptedCRT = rsaDecryptCRT(cipher, d, p, q);
long timeCRT = System.nanoTime() - startCRT;
// 标准解密
long startStd = System.nanoTime();
BigInteger decryptedStd = rsaDecryptStandard(cipher, d, n);
long timeStd = System.nanoTime() - startStd;
System.out.println("Original: " + message);
System.out.println("CRT decrypted: " + decryptedCRT + " (" + timeCRT / 1000 + " us)");
System.out.println("Standard decrypted: " + decryptedStd + " (" + timeStd / 1000 + " us)");
System.out.println("Speedup: " + (double)timeStd / timeCRT + "x");
}
}
Java实现：扩展CRT（模数不互质的情况）
public class ExtendedCRT {
/**
* 扩展CRT: 处理模数不互质的情况
* 方程组 x ≡ a[i] (mod m[i])
* 有解条件: 对所有i,j, (a[i]-a[j]) % gcd(m[i],m[j]) == 0
* @return [解, 最小公倍数] 或 null (无解)
*/
public static long[] solveExtendedCRT(long[] a, long[] m) {
long x = a[0]; // 当前解
long M = m[0]; // 当前模数 (LCM)
for (int i = 1; i < a.length; i++) {
long[] eg = exGcd(M, m[i]);
long g = eg[0];
long p = eg[1]; // p*M + q*m[i] = g
// 检查是否有解
if ((a[i] - x) % g != 0) {
return null; // 无解
}
// 合并: x = x + M * ((a[i]-x)/g * p mod (m[i]/g))
long diff = (a[i] - x) / g;
long mod = m[i] / g;
long t = ((diff % mod) * (p % mod) % mod + mod) % mod;
x = x + M * t;
M = M / g * m[i]; // LCM
x = (x % M + M) % M;
}
return new long[]{x, M};
}
static long[] exGcd(long a, long b) {
if (b == 0) return new long[]{a, 1, 0};
long[] r = exGcd(b, a % b);
return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
}
public static void main(String[] args) {
// 模数不互质的例子
long[] a = {2, 3, 2};
long[] m = {4, 6, 5}; // 4和6不互质
long[] result = solveExtendedCRT(a, m);
if (result != null) {
System.out.println("Solution: x ≡ " + result[0] + " (mod " + result[1] + ")");
// 验证
for (int i = 0; i < a.length; i++) {
System.out.println(result[0] + " % " + m[i] + " = " + (result[0] % m[i]));
}
} else {
System.out.println("No solution exists");
}
}
}
应用场景：秘密共享方案
import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;
public class ShamirSecretSharing {
/**
* 基于CRT的(k,n)门限秘密共享
* 选择n个两两互质的模数，秘密为S
* 任意k个份额可重构秘密，k-1个无法获得任何信息
*/
static class Share {
BigInteger value;
BigInteger modulus;
Share(BigInteger v, BigInteger m) { this.value = v; this.modulus = m; }
}
static List<Share> splitSecret(BigInteger secret, int n, int k) {
// 选择n个递增的互质模数
BigInteger[] moduli = new BigInteger[n];
BigInteger base = secret.add(BigInteger.ONE);
for (int i = 0; i < n; i++) {
moduli[i] = base.add(BigInteger.valueOf(i));
// 确保互质 (简化处理，实际应选素数)
}
// 确保秘密 < 前k个模数的最小乘积
BigInteger minProduct = BigInteger.ONE;
for (int i = 0; i < k; i++) {
minProduct = minProduct.multiply(moduli[i]);
}
if (secret.compareTo(minProduct) >= 0) {
throw new IllegalArgumentException("Secret too large");
}
List<Share> shares = new ArrayList<>();
for (int i = 0; i < n; i++) {
shares.add(new Share(secret.mod(moduli[i]), moduli[i]));
}
return shares;
}
static BigInteger reconstructSecret(List<Share> shares) {
BigInteger[] rems = new BigInteger[shares.size()];
BigInteger[] mods = new BigInteger[shares.size()];
for (int i = 0; i < shares.size(); i++) {
rems[i] = shares.get(i).value;
mods[i] = shares.get(i).modulus;
}
return CRTRSA.solveCRTBig(rems, mods);
}
}
复杂度分析
| 指标 | 标准实现 | CRT加速 |
|---|---|---|
| 时间复杂度 | $O(n \cdot \log M)$ | $O(k \cdot \log M)$ (k为份额数) |
| 空间复杂度 | $O(1)$ | $O(1)$ |
| RSA解密加速 | $O(\log^3 n)$ | $O(\log^3 p) + O(\log^3 q)$ (约4x快) |
历史与现代价值
中国剩余定理跨越两千余年仍焕发活力：
– 古代: 《孙子算经》解决军队点兵、历法推算等实际问题
– 近代: 成为抽象代数中环论的同构定理特例
– 现代: RSA-OAEP、Paillier同态加密等方案的性能基石
– 未来: 全同态加密、安全多方计算的核心组件
掌握CRT的实现细节与扩展技巧，是深入理解现代密码学体系的关键一步。
