中国剩余定理学习笔记

本文最后更新于:2022年7月21日 下午

中国剩余定理学习笔记

[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)