L02e 中国剩余定理:一个大表盘拆成几个小表盘
从「物不知数」这道古题讲起,看清中国剩余定理说了什么、两个前提为什么缺一不可,再学会逐步代入和构造两种解法,最后用它给大数模运算提速。
一句话版
只知道一个数除以 3 余几、除以 5 余几、除以 7 余几,能不能把这个数找回来?中国剩余定理说能,只要这几个除数两两互素,在 0 到它们的乘积之间,答案有且只有一个。反过来用,一个大模数上的运算可以拆成几个小模数上分别算,最后再合并。
这一页用到 L02c 的模逆和 L02d 的欧拉定理。这是本讲最后一块零件,学完就能看懂 RSA 用到的全部数论。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| CRT | Chinese Remainder Theorem,中国剩余定理 | 由几个余数反推原来的数 |
| 同余方程组 | system of congruences | 几条 x ≡ aᵢ (mod nᵢ) 同时成立 |
| 两两互素 | pairwise coprime | 任取两个数,gcd 都是 1 |
| 模数 | modulus,复数 moduli | 每条同余式里的除数 |
| N | 模数之积 | 所有模数乘起来,解在 0 到 N − 1 之间唯一 |
| 逐步代入法 | successive substitution | 一条一条把同余式代进去解 |
一个类比:用两个小表盘给一个大表盘定位
一个刻了 15 格的大表盘,指针停在某一格,你看不到。旁边有两个小表盘,一个 3 格,一个 5 格,它们和大表盘一起转。
你能看到小表盘指在哪里:3 格的指在 2,5 格的指在 3。只凭这两个读数,就能断定大表盘指在 8。原因是 0 到 14 这十五个数,在两个小表盘上的读数组合两两不同,一个读数组合只对应一个数。
小表盘的格数必须互素。如果换成 3 格和 6 格,它们的读数会「绑在一起」:6 格的读数一旦确定,3 格的读数也跟着确定,两个表盘合起来只能区分 6 种情况,定位不了 18 格的大表盘。
类比在哪里失效:
- 真实问题里,小表盘可能有三个、四个,类比只画了两个。道理一样,只是要求任意两个都互素。
- 表盘告诉你答案唯一,没告诉你怎么快速找到它。15 格可以一格格对,模数一大就得用第 2、3 个概念里的算法。
从零讲起
1. 中国剩余定理说了什么
它解决什么问题
已知一个数除以几个数的余数,要把这个数找回来。这件事在古代用来数兵、排历法,在今天用来给大数运算提速。
从哪来(补充)
最早的陈述见于《孙子算经》里的「物不知数」题,Wikipedia 把这本书定在公元 3 到 5 世纪。秦九韶在 1247 年的《数书九章》里给出了完整的「大衍术」解法。课件写的是约公元 100 年,和这个说法不一致,考试照课件答。
出处:Wikipedia: Chinese remainder theorem
直觉
把 0 到 14 每个数除以 3、除以 5 的余数都写出来,看能不能找到两个数余数完全一样。找不到。十五个数,十五种余数组合,一一对应。所以只要报出余数组合,就能唯一地报出这个数。
一步一步看
目标:把 0 到 14 除以 3 和除以 5 的余数排成两行,看出每种余数组合在 15 以内只对应一个数。
-
列出 0 到 14,下面两行分别写它除以 3、除以 5 的余数。
-
第二行每 3 格重复一次,第三行每 5 格重复一次。
-
两行要同时重复,得等到 3 和 5 的公倍数,也就是 15。所以在 0 到 14 之内,余数组合不会重复。
-
给出余数组合 (2, 3),只有 8 对得上。
怎么判断
若 n₁, …, n_k 两两互素,N = n₁ × … × n_k,0 ≤ aᵢ < nᵢ,
则存在唯一的 x,0 ≤ x < N,使 x ≡ aᵢ (mod nᵢ) 对每个 i 成立
意思是:除数两两互素时,给定每个除数下的余数,在 0 到 N − 1 之间正好有一个数满足全部条件。
两个前提缺一不可。
- 两两互素:x ≡ 1 (mod 4) 和 x ≡ 2 (mod 6) 无解。第一式要求 x 是奇数,第二式要求 x 是偶数,矛盾出在 4 和 6 共有的因子 2 上。模数互素时就不会出现这种冲突。
- 限定范围:23 和 128 都满足物不知数的三个条件。唯一性只在 0 到 N − 1 之间成立,所以答案要写成 x ≡ 23 (mod 105),而不是只写 23。
「两两互素」不能放宽成「整体互素」。6、10、15 三个数整体的 gcd 是 1,但任意两个都有公因数,不能直接套本讲的定理。
常见误解
以为模数不互素就一定无解
不一定。模数不互素时,余数之间兼容就可能有解,只是解按最小公倍数重复,不再按乘积唯一。本讲只讲两两互素的情形。
答案只写一个数
CRT 给的是模 N 的唯一解。物不知数的答案是 x ≡ 23 (mod 105),23、128、233 都满足条件。
试一下
在 0 到 14 之间,找一个除以 3 余 1、除以 5 余 4 的数。
除以 5 余 4 的有 4、9、14。其中除以 3 余 1 的是 4。答案 x ≡ 4 (mod 15)。
模数 4、9、25 能直接用中国剩余定理吗?
能。4 = 2²、9 = 3²、25 = 5²,任意两个都没有公因数,两两互素。N = 900。
2. 逐步代入法
它解决什么问题
定理只说答案存在且唯一,要真正求出来,需要一个能照着做的方法。逐步代入法每次只处理一条同余式,适合两三条同余式的手算。
直觉
一条条加条件往下筛。先写出所有满足第一条的数,再从里面挑出满足第二条的,再挑出满足第三条的。每加一条,剩下的数间隔变大,最后间隔等于全部模数之积。
一步一步看
目标:把物不知数的三条同余式逐条代入,看出候选数的间隔从 3 变 15 再变 105,最后锁定 23。
解物不知数:x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7)。
-
满足第一条的数:2、5、8、11、14、17、20、23……每隔 3 一个,写成 x = 3t + 2。
-
代入第二条:3t + 2 ≡ 3 (mod 5),即 3t ≡ 1 (mod 5)。3 模 5 的逆元是 2,所以 t ≡ 2 (mod 5)。
-
设 t = 5s + 2,代回得 x = 15s + 8。现在剩下的数每隔 15 一个。
-
代入第三条:15s + 8 ≡ 2 (mod 7)。15 ≡ 1、8 ≡ 1 (mod 7),所以 s + 1 ≡ 2,s ≡ 1。
-
设 s = 7u + 1,代回得 x = 105u + 23。答案 x ≡ 23 (mod 105)。
怎么算
① 用第一条参数化:x = n₁·t + a₁
② 代入第二条,得到 t 的同余式,用模逆解出 t
③ 把 t 参数化,代回 x
④ 重复直到用完所有同余式,最终 x = N·u + x₀,答案 x ≡ x₀ (mod N)
意思是:每次把 x 写成「某个模数的倍数加一个已知数」,代进下一条同余式解出新参数,直到所有条件都用上。
第 ② 步就是解形如 c·t ≡ d (mod m) 的方程,两边乘 c 的模逆即可。小数字可以试,大数字要用扩展欧几里得,这是本讲把模逆排在 CRT 前面的原因。
常见误解
代入后忘了先把系数化简
15s + 8 ≡ 2 (mod 7) 里,先把 15 和 8 分别模 7,得 s + 1 ≡ 2,一眼就能解。不化简直接去求 15 模 7 的逆元,多算一步还容易错。
解出 t 后直接把 t 当答案
t 只是中间参数。解出 t ≡ 2 (mod 5) 后要写 t = 5s + 2 代回 x,x 才是答案。
试一下
用逐步代入法解 x ≡ 1 (mod 3)、x ≡ 2 (mod 4)。
设 x = 3t + 1,代入第二条:3t + 1 ≡ 2 (mod 4),3t ≡ 1 (mod 4)。3 × 3 = 9 ≡ 1,所以 t ≡ 3。设 t = 4s + 3,x = 12s + 10。答案 x ≡ 10 (mod 12)。验算:10 mod 3 = 1,10 mod 4 = 2。
用逐步代入法解 x ≡ 2 (mod 5)、x ≡ 3 (mod 7)。
设 x = 5t + 2,代入:5t + 2 ≡ 3 (mod 7),5t ≡ 1。5 模 7 的逆元是 3,t ≡ 3。设 t = 7s + 3,x = 35s + 17。答案 x ≡ 17 (mod 35)。验算:17 mod 5 = 2,17 mod 7 = 3。
3. 构造法:孙子的算法
它解决什么问题
逐步代入法每次只能处理一条,同余式一多就要来回代很多轮。构造法一次把所有条件拼起来,适合模数多的情况,也正是《孙子算经》原文用的方法。
直觉
为每个模数准备一个「基元」:它在自己的模数下余 1,在其他模数下都余 0。把每个基元乘上对应的余数再加起来,在每个模数下看,只有自己那一项留下余数,其他项都是 0。
一步一步看
目标:按孙子的算法给每个模数找基元再加权相加,看出构造法同样得到 23。
还是物不知数,余数分别是 2、3、2。
-
找模 3 的基元:要被 5 和 7 整除,又除以 3 余 1。35 除以 3 余 2,不行;70 除以 3 余 1,就是它。
-
找模 5 的基元:要被 3 和 7 整除,又除以 5 余 1。21 除以 5 余 1,就是它。
-
找模 7 的基元:要被 3 和 5 整除,又除以 7 余 1。15 除以 7 余 1,就是它。
-
乘上各自的余数:2 × 70 = 140,3 × 21 = 63,2 × 15 = 30。
-
加起来得 233,再减去 105 的倍数:233 − 210 = 23。
怎么算
Nᵢ = N / nᵢ,基元 eᵢ = Nᵢ × (Nᵢ⁻¹ mod nᵢ)
x = a₁·e₁ + a₂·e₂ + … + a_k·e_k (mod N)
意思是:每个模数的基元,是「其他模数之积」再乘上它在本模数下的逆元;余数乘基元再求和,最后对 N 取模,就是答案。
对照《孙子算经》原文:「三三數之賸二,置一百四十;五五數之賸三,置六十三;七七數之賸二,置三十;并之得二百三十三,以二百一十減之,即得。」
| 古文 | 现代记法 |
|---|---|
| 三三數之賸二,置一百四十 | 2 × 70 = 140 |
| 五五數之賸三,置六十三 | 3 × 21 = 63 |
| 七七數之賸二,置三十 | 2 × 15 = 30 |
| 并之得二百三十三 | 140 + 63 + 30 = 233 |
| 以二百一十減之 | 233 − 210 = 23 |
求基元时的逆元,模数大了一样要用扩展欧几里得。
常见误解
以为基元直接取「其他模数之积」
模 3 的基元不是 35,35 除以 3 余 2。要再乘上 35 模 3 的逆元 2,得 70,才满足除以 3 余 1。
以为最后一步一定减 210
210 是 105 的 2 倍,只是这道题刚好要减两次。规则是减去 N 的倍数,直到落进 0 到 N − 1。
试一下
只把物不知数里「七七數之賸二」改成「賸三」,答案变成多少?
只有第三项变:3 × 15 = 45。140 + 63 + 45 = 248,248 − 210 = 38。验算:38 mod 3 = 2,38 mod 5 = 3,38 mod 7 = 3。
求模 3、模 4 的两个基元。
模 3 的基元要被 4 整除、除以 3 余 1:4 本身就行。模 4 的基元要被 3 整除、除以 4 余 1:9。
4. 用 CRT 给大数模运算提速
它解决什么问题
课件把这一部分的标题写成「大数的高效模运算」。在密码学里,CRT 主要是加速工具:一个大模数上的乘方,拆成几个小模数上分别算,数字小得多,算完再合并。
直觉
模 15 的表盘太大,就拆成模 3 和模 5 两个小表盘。在每个小表盘上,底数可以先化简,指数可以用欧拉定理降下来。两个小答案拿到以后,用逐步代入法合成大答案。
一步一步看
目标:把 7¹⁰ mod 15 拆成模 3、模 5 两路小算再合并,看结果和直接验算是否一致。
算 7¹⁰ mod 15。
-
拆模数:15 = 3 × 5,两者互素。
-
分两路算,结果列在下表。
路线 底数化简 降指数 结果 模 3 7 ≡ 1 1 的任何次方都是 1 1 模 5 7 ≡ 2 φ(5) = 4,10 mod 4 = 2 2² = 4 -
合并 x ≡ 1 (mod 3)、x ≡ 4 (mod 5):设 x = 5t + 4,代入得 5t + 4 ≡ 1 (mod 3),即 2t ≡ 0,t ≡ 0。
-
所以 x ≡ 4 (mod 15)。
-
直接验算:7² = 49 ≡ 4,7⁴ ≡ 16 ≡ 1,7¹⁰ = 7⁸ × 7² ≡ 4 (mod 15),对得上。
怎么算
① 拆模数:N = n₁ × n₂,确认互素
② 分路:在每个 nᵢ 下化简底数,用欧拉定理降指数
③ 合并:用逐步代入法或构造法把各路结果合成模 N 的答案
意思是:先拆,再在小模数上分别算,最后用 CRT 拼回去。
RSA 解密时,持有私钥的一方知道 n = pq 里的 p 和 q,就可以分别在模 p 和模 q 下算,再用 CRT 合并。这叫 RSA-CRT,速度大约快 4 倍,生产级 RSA 库都这么做。
常见误解
以为拆开以后两路的指数一样降
每一路按自己的模数降。模 5 用 φ(5) = 4,模 3 用 φ(3) = 2,不能都用 φ(15)。
以为任何人都能用 RSA-CRT 加速
拆模数要知道 p 和 q,只有私钥持有者知道。只拿到公钥 n 的人拆不开,这正是 RSA 的安全前提。
试一下
用 CRT 算 2¹⁰ mod 21。
21 = 3 × 7。模 3:2 ≡ −1,(−1)¹⁰ = 1。模 7:φ(7) = 6,10 mod 6 = 4,2⁴ = 16 ≡ 2。合并 x ≡ 1 (mod 3)、x ≡ 2 (mod 7):设 x = 7t + 2,7t + 2 ≡ 1 (mod 3),t + 2 ≡ 1,t ≡ 2,x = 21s + 16。答案 16。验算:2¹⁰ = 1024 = 48 × 21 + 16。
算 4⁵ mod 15,先拆再合。
模 3:4 ≡ 1,结果 1。模 5:4 ≡ −1,(−1)⁵ = −1 ≡ 4。合并 x ≡ 1 (mod 3)、x ≡ 4 (mod 5),上面例子已算出 x ≡ 4 (mod 15)。验算:4⁵ = 1024 = 68 × 15 + 4。
把它们串起来
中国剩余定理说,两两互素的模数下给定余数,在 0 到乘积之间有唯一解。逐步代入法一条一条筛,适合手算;构造法一次拼出答案,适合模数多。反过来用,大模数上的运算可以拆到小模数上分头算,这就是它在密码学里的用处。
整讲四块零件在 RSA 里汇合,如下图。
L02b 的欧几里得算法判断 e 和 φ(n) 互素;L02c 的扩展欧几里得由 e 求出 d;L02d 的欧拉定理保证解密还原消息;这一页的 CRT 负责加速。
课件里的坑
- [口径差异] 课件 p.40 写 CRT 相传由孙子在约公元 100 年发现 → Wikipedia 把《孙子算经》定在公元 3 到 5 世纪,两种说法不一致,考试照课件答(p.40)
- [适用条件] 课件 p.42 要求模数两两互素 → 不能弱化成整体互素,6、10、15 整体 gcd 为 1 也不能直接套(p.42)
- [容易漏看] 课件 p.43 最后写成 x = 105u + 23 → 答案应写 x ≡ 23 (mod 105),只写 23 会丢掉「模 N 唯一」这层意思(p.43)
- [容易漏看] 课件 p.43 解 3t ≡ 1 (mod 5) 时用的是「查模 5 的乘法表」→ 模数大时这一步就是求模逆,要用扩展欧几里得(p.43)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 CRT 的两个前提和逐步代入四步;再把物不知数用两种方法各解一遍;最后做变式题,回查最容易错的地方:合并后忘了回代验算两个同余式。
必背
- CRT 两个前提缺一不可:模数两两互素、解限定在 0 ≤ x < N;答案要写成 x ≡ x₀ (mod N) 而不是单个数。
- 两两互素不能弱化成整体互素:6、10、15 三个数整体 gcd 为 1,但任意两个都不互素。
- CRT 逐步代入模板:参数化 → 代入下一式解模逆 → 再参数化,最终形式 x = N·u + x₀。
- 物不知数的解是 x ≡ 23 (mod 105);构造法基元 70、21、15,140 + 63 + 30 = 233,减 210 得 23。
- CRT 在密码学里是加速工具:RSA 解密分别在模 p、模 q 下算再合并,叫 RSA-CRT。
- 20³⁷ mod 77 = 48:拆成模 7 余 6、模 11 余 4 再合并。
课件例题
例 1(课件 p.41、p.43):物不知数,用两种方法解
题面:《孫子算經》原题「今有物不知其數,三三數之賸二,五五數之賸三,七七數之賸二,問物幾何?」翻成同余式就是 x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7)。
提示
逐步代入法从 x = 3t + 2 开始。构造法先找三个「自己这里余 1、别处余 0」的数。
解答
逐步代入法(p.43):设 x = 3t + 2,代入第二式得 3t ≡ 1 (mod 5),t ≡ 2。设 t = 5s + 2,得 x = 15s + 8。代入第三式:15 ≡ 1、8 ≡ 1 (mod 7),得 s + 1 ≡ 2,s ≡ 1。设 s = 7u + 1,得 x = 105u + 23。答案 x ≡ 23 (mod 105),解为 23, 128, 233, …
构造法(p.41 古文):70 模 3 余 1,又被 5、7 整除;21 模 5 余 1,又被 3、7 整除;15 模 7 余 1,又被 3、5 整除。乘上各自的余数再相加:2 × 70 + 3 × 21 + 2 × 15 = 140 + 63 + 30 = 233。减去 210 = 2 × 105,得 23。
例 2(课件 p.44,Exercise-6):解 x ≡ 3 (mod 5)、x ≡ 4 (mod 7)
题面:用逐步代入法解这组同余式。
提示
代入后要解 5t ≡ 1 (mod 7),5 模 7 的逆元在 L02c 例 1 里算过。
解答
设 x = 5t + 3,代入第二式:5t + 3 ≡ 4,即 5t ≡ 1 (mod 7)。5⁻¹ mod 7 = 3,所以 t ≡ 3。设 t = 7s + 3,得 x = 35s + 18。答案 x ≡ 18 (mod 35)。验算:18 mod 5 = 3,18 mod 7 = 4。
例 3(课件 p.51,Exercise-11):用 CRT 算 20³⁷ mod 77
题面:用中国剩余定理计算 20³⁷ mod 77,课件提示先分别算模 7 和模 11。
提示
77 = 7 × 11。模 7 下 20 ≡ −1,模 11 下 20 ≡ −2。
解答
20³⁷ ≡ 48 (mod 77)。完整过程见下方完整例题。
完整例题
这道课件 Exercise-11 是整讲的集大成之作:素数分解、欧拉定理降指数、解模逆、CRT 合并全用上了。
题面:用 CRT 计算 20³⁷ mod 77。
解法:
- 拆模数:77 = 7 × 11,两者互素,符合 CRT 前提。
- 模 7 这一路:20 ≡ 6 ≡ −1 (mod 7),故 20³⁷ ≡ (−1)³⁷ = −1 ≡ 6 (mod 7)。
- 模 11 这一路:20 ≡ 9 ≡ −2 (mod 11),φ(11) = 10,用欧拉定理降指数,37 mod 10 = 7,故 20³⁷ ≡ (−2)⁷ = −128;128 = 11 × 11 + 7,所以 −128 ≡ −7 ≡ 4 (mod 11)。
- 合并 x ≡ 6 (mod 7)、x ≡ 4 (mod 11):设 x = 11k + 4,代入得 11k + 4 ≡ 6 (mod 7),即 4k ≡ 2 (mod 7),解出 k ≡ 4 (mod 7)(4 × 4 = 16 ≡ 2 ✓)。
- 设 k = 7m + 4,得 x = 77m + 48,即 20³⁷ ≡ 48 (mod 77)。验算 48 mod 7 = 6 ✓、48 mod 11 = 4 ✓。
要点:直接算 20³⁷ 是个 49 位数,拆开后每一步都在两位数范围内。RSA-CRT 解密用的就是这个套路。
答题格式:先写「77 = 7 × 11 且互素」交代为什么能用 CRT;两路各写一行降指数的依据;合并后回代验算两个同余式。
变式题(先自己做)
改编自课件 p.51:用 CRT 计算 3¹⁰⁰ mod 35。
提示
拆完模数以后,两边的指数都还是 100,先想想用什么把它降下来。
判分点与答案(非官方评分标准)
判分点:① 交代 35 = 5 × 7 互素 ② 两路都用欧拉定理降指数,不逐次硬乘 ③ 合并后回代验算两个同余式。
- 模 5:φ(5) = 4,100 mod 4 = 0,故 3¹⁰⁰ = (3⁴)²⁵ ≡ 1 (mod 5)。
- 模 7:φ(7) = 6,100 = 6 × 16 + 4,故 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7)。
- 合并:设 x = 7k + 4,代入 7k + 4 ≡ 1 (mod 5),即 2k ≡ 2 (mod 5),解出 k ≡ 1 (mod 5)。设 k = 5m + 1,得 x = 35m + 11,即 3¹⁰⁰ ≡ 11 (mod 35)。
- 验算:11 mod 5 = 1 ✓、11 mod 7 = 4 ✓。
闪卡自测
1. CRT 的两个前提是什么?举一个模数不互素导致无解的例子。
模数两两互素;解在 0 ≤ x < N 范围内唯一。x ≡ 1 (mod 4) 与 x ≡ 2 (mod 6) 无解:前者要 x 为奇数,后者要 x 为偶数,冲突出在公因数 2 上(p.40、p.42)。
2. 《孫子算經》里的 140、63、30 是怎么来的?为什么最后减 210?
70、21、15 分别是在模 3、模 5、模 7 下余 1、又被另外两个模数整除的数,乘上各自余数 2、3、2 得 140、63、30。相加得 233,再减去 210 = 2 × 105 做模 N 归约,得 23(p.41)。
3. 逐步代入法的四步是什么?哪一步要用模逆?
参数化 → 代入下一式解出参数 → 再参数化回代 → 重复到用完所有同余式。解参数那一步要用模逆,模数大时用扩展欧几里得(p.43)。
4. 为什么 x ≡ 3 (mod 5)、x ≡ 4 (mod 7) 的解要写成模 35?
N = 5 × 7 = 35,CRT 只保证 0 到 34 之间唯一。18、53、88 都满足条件,所以写 x ≡ 18 (mod 35)(p.44)。
5. 为什么 CRT 能给大数模运算提速?
它把模 N 的运算拆成几个小模数上的运算,算完再合并。RSA 解密时知道 p、q,就能分别在模 p 和模 q 下算,这叫 RSA-CRT(p.39、p.42)。
6. 20³⁷ mod 77 拆开后两路各得多少?
模 7 下 20 ≡ −1,得 6;模 11 下 20 ≡ −2,指数降到 7,得 4。合并为 48(p.51)。
下一讲
下一讲 L03a 进入密码学本身,RSA 的密钥生成和解密会直接调用本讲的四块零件。去之前把完整例题独立重做一遍,做到不看步骤能写全。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。