中国剩余定理学习笔记

[TOC]

中国剩余定理（Chinese Remainder Theorem, CRT）是一种求解一元线性同余方程组的方法。其中，“同余”指的是两个数mod n得到的余数相同，因此剩余定理也可以被叫做余数定理。

形式描述

维基百科上给出的形式描述如下：

对于一元线性同余方程组$(S)$：

$$(S)= \left\{ \begin{array}{lr} x \equiv a_1 (mod\ m_1)&\\ x \equiv a_2 (mod\ m_2)&\\ \dots &\\ x \equiv a_n (mod\ m_n)& \end{array} \right.$$

假如整数$m_1,m_2,\dots,m_n$任意两数互质，则方程组$(S)$有解，且解法如下：

1. 设$M=m_1\times m_2 \times \dots \times m_n = \prod^{n}_{i=1}m_i$，设$M_i=M/m_i$。
2. 设$t_i=M^{-1}_i$，即$t_iM_i\equiv 1\ (mod\ m_i)$
3. 则通解为$x=kM+\sum^{n}_{i=1}a_i t_i M_i,\ k \in Z$。

理解

根据知乎回答[1]对这个定理的理解：

设问题为：求整数$x$使满足$x\ mod\ 3=2, x\ mod\ 5=3, x\ mod\ 7=2$。

直接代入公式可以算出$x=233+k\times 105$。

但是我们可以先把原始问题分解成第二层这三个问题，$x=x_1+x_2+x_3$就是解。而第二层的问题又可以有一个等价问题（第三层）。

以y1满足除以3余1 除以5余0 除以7余0为例，y1一定是$(5\times 7)$的倍数，那就是$y_1 = 35M_i\equiv 1(mod\ 3)$，对应着公式的第二步。其他两个问题同理，能解出$M_i$，进而得到$y_i$，然后按照流程图推回去得到$x$。

graph TD
A[整数x满足除以3余2 除以5余3 除以7余2]
A --> B[x1满足除以3余2 除以5余0 除以7余0]
A --> C[x2满足除以3余0 除以5余3 除以7余0]
A --> D[x3满足除以3余0 除以5余0 除以7余2]
B --> E[y1满足除以3余1 除以5余0 除以7余0 x1=2*y1]
C --> F[y2满足除以3余0 除以5余1 除以7余0 x2=3*y2]
D --> G[y3满足除以3余0 除以5余0 除以7余1 x3=2*y3]

应用

维基百科[3]上介绍这个定理可以用于快速傅里叶变化、加密、Range ambiguity resolution、证明哥德尔不完备定理等，其中详细介绍CRT在密码学中应用如下：

RSA实现中的计算

RSA算法在解密的时候需要计算$m=c^d$，$d$是一个比较大的数。为了简化这个计算，会先使用已知的两个大素数$p,q$计算$d_p=d\ mod \ (p-1), d_q=d\ mod \ (q-1), q_{inv}=q^{-1}\ mod\ p$。然后在解密的时候计算：$m_1=c^{dp}\ mod\ p, m_2=c^{dq}\ mod\ q, h=q_{inv}(m_1-m_2)\ mod\ p, m=m_2+hq\ mod \ p* q$。

密钥共享

密钥共享指的是秘钥管理者将密钥$S$拆分成一堆子密钥$s_i$，然后把他们分发给各个成员，只有当大于某个数个成员把子密钥放在一起时，才能恢复出秘钥$S$。比如发射核弹的权限掌握在ABC三个人手中，其中任意两个人决定发射核弹时，核弹就能发射，此时核弹发射的密钥分成了三个子密钥，而只要其中任意两个子密钥就能恢复出密钥。

实现的方法是：选择$n$个互质的整数$m_1<m_2<...<m_n$，再，令$S$大于$k-1$个$m$的连乘，小于$k$个$m$的连乘，$k$个子密钥就能恢复出密钥，而子密钥$s_i=S\ mod \ m_i \ (i=1,2,...,n)$。

参考文献：

[1] 中国剩余定理（CRT ） - 知乎 (zhihu.com)

[2] 中国剩余定理 - 维基百科，自由的百科全书 (wikipedia.org)

[3] Chinese remainder theorem - Wikipedia

[4] 三体与密码学 | 秘密共享 (Secret Sharing) 详解 - 哔哩哔哩 (bilibili.com)

[5] [secret sharing_百度百科 (baidu.com)](https://baike.baidu.com/item/secret sharing/4406854?fr=aladdin)