中国剩余定理

Chinese Remainder Theorem (CRT).

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

— 孙子算经

The Chinese remainder theorem (CRT) is a theorem which gives a unique solution to a simultaneous linear congruences with coprime moduli. In its basic form, the CRT will determine a number $p$ that, when divided by some given divisors, leaves given remainders.

If $m_1,...,m_k$ are pairwise coprime, i.e., $\gcd(m_i,m_j)=1$ for $i\neq j$ , then the following system

\begin{cases} \ x\equiv a_1 \pmod{m_1} \\ \ x\equiv a_2 \pmod{m_2} \\ \ ..., \\ \ x\equiv a_k \pmod{m_k} \end{cases}

has exactly one solution in the sense of module $M=\Pi_{i=1}^k m_i$ for any $a_1,a_2,...,a_k\in \mathbb{Z}$ .

We define $M_i=M/m_i$ and $t_i\equiv M_i^{-1}\pmod{m_i}$ , then the solution to this congruences is $x\equiv \sum_{i=1}^k a_iM_it_i \pmod{M}$ . Note that $x$ is unique modulo $M$ .

The proof of correctness and uniqueness of CRT: My CnBlogs or OI Wiki-CRT

Code Implementation

cpp

long long CRT(int k, long long* a, long long* m) {
    long long M = 1, ans = 0;
    for (int i = 1; i <= k; ++i)
        M = M * m[i];
	for (int i = 1; i <= k; ++i) {
        long long Mi = M / m[i], ti, _;
        exgcd(Mi, m[i], ti, _); // get inverse: ti * Mi mod m[i] = 1
        ans = (ans + a[i] * Mi % M * ti % M) % M;
    }
    return (ans % M + M) % M;
}

Eureka moment!

数论的定理多如牛毛，在众多熟悉或不熟悉的外国名字中看到一个「中国」剩余定理还是非常之亲切的。

CRT 提供了互质模数的线性同余方程组的解。在密码学中 CRT 经常被运用于简化模意义下求幂的运算。具体来说，对于合数模数 $M$ 且 $\gcd(M,a)\neq 1$ 的情况，可以应用 CRT 简化 $a^e\mod{M}$ 的计算。此外，CRT 还能用于加速 RSA 的解密过程 (RSA decryption)。

m=c^d\mod{N} \Rightarrow \begin{cases} m\equiv c^d\mod{p} \\m\equiv c^d \mod{q} \end{cases} \Rightarrow \begin{cases} m\equiv (c\mod p)^{d\mod{(p-1)}}\mod{p}\\ m\equiv (c\mod q)^{d\mod{(q - 1)}}\mod{q} \end{cases}

Bob (Receiver) 是知道 $N$ 的两个 factor $p$ 与 $q$ 的，因此其先将朴素的解密过程转化为这一线性同余方程组，并应用 CRT 得到方程的解，也即消息 $m$ 。这一解密方式比直接计算 $c^d\mod{N}$ 快了 $4$ 倍左右。

P.S. RSA 问题是一个著名的困难问题 (hard problems)，我将会在 P3 中进行介绍。