← COMP5521 全部讲次
L02e · 第 2 周

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 以内只对应一个数。

  1. 列出 0 到 14,下面两行分别写它除以 3、除以 5 的余数。

    三行表格。第一行 x 从 0 到 14;第二行 x mod 3,按 0、1、2 循环;第三行 x mod 5,按 0、1、2、3、4 循环。8 那一列被青绿框出,读数是 (2, 3)。说明文字:十五个数的余数对两两不同,给出余数对 (2, 3),0 到 14 里只有 8 对得上;3 和 5 互素,3 × 5 = 15,所以刚好一一对应

  2. 第二行每 3 格重复一次,第三行每 5 格重复一次。

  3. 两行要同时重复,得等到 3 和 5 的公倍数,也就是 15。所以在 0 到 14 之内,余数组合不会重复。

  4. 给出余数组合 (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)。

  1. 满足第一条的数:2、5、8、11、14、17、20、23……每隔 3 一个,写成 x = 3t + 2。

  2. 代入第二条:3t + 2 ≡ 3 (mod 5),即 3t ≡ 1 (mod 5)。3 模 5 的逆元是 2,所以 t ≡ 2 (mod 5)。

    三排数字往下筛。第一排是满足 x ≡ 2 (mod 3) 的 2、5、8、11、14、17、20、23、26、29、32、35、38,每隔 3 一个;第二排再要求 ≡ 3 (mod 5),留下 8、23、38、53、68、83、98、113、128,每隔 15 一个,x = 15s + 8;第三排再要求 ≡ 2 (mod 7),留下 23、128、233,每隔 105 一个,x = 105u + 23。底部写着最小的是 23,答案写成 x ≡ 23 (mod 105)

  3. 设 t = 5s + 2,代回得 x = 15s + 8。现在剩下的数每隔 15 一个。

  4. 代入第三条:15s + 8 ≡ 2 (mod 7)。15 ≡ 1、8 ≡ 1 (mod 7),所以 s + 1 ≡ 2,s ≡ 1。

  5. 设 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。

  1. 找模 3 的基元:要被 5 和 7 整除,又除以 3 余 1。35 除以 3 余 2,不行;70 除以 3 余 1,就是它。

  2. 找模 5 的基元:要被 3 和 7 整除,又除以 5 余 1。21 除以 5 余 1,就是它。

  3. 找模 7 的基元:要被 3 和 5 整除,又除以 7 余 1。15 除以 7 余 1,就是它。

    一张四列表格,行是三个基元 70、21、15,列是 mod 3、mod 5、mod 7 下的余数和乘余数一栏。70 那行余数是 1、0、0,乘余数得 2 × 70 = 140;21 那行是 0、1、0,得 3 × 21 = 63;15 那行是 0、0、1,得 2 × 15 = 30。底部写着 140 + 63 + 30 = 233,233 − 2 × 105 = 23,余数 2、3、2 分别乘到三个基元上,最后减掉 105 的倍数落进 0 到 104

  4. 乘上各自的余数:2 × 70 = 140,3 × 21 = 63,2 × 15 = 30。

  5. 加起来得 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。

  1. 拆模数:15 = 3 × 5,两者互素。

  2. 分两路算,结果列在下表。

    路线 底数化简 降指数 结果
    模 3 7 ≡ 1 1 的任何次方都是 1 1
    模 5 7 ≡ 2 φ(5) = 4,10 mod 4 = 2 2² = 4
  3. 合并 x ≡ 1 (mod 3)、x ≡ 4 (mod 5):设 x = 5t + 4,代入得 5t + 4 ≡ 1 (mod 3),即 2t ≡ 0,t ≡ 0。

  4. 所以 x ≡ 4 (mod 15)。

  5. 直接验算: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 里汇合,如下图。

四列零件汇进下方的 RSA 框:Part 1 的欧几里得算法判互素,Part 2 的扩展欧几里得由 e 求出 d 使 ed ≡ 1 (mod φ(n)),Part 3 的欧拉定理提供 φ(n) = (p−1)(q−1) 与解密正确性,Part 4 的 CRT 只负责加速也就是 RSA-CRT

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 的两个前提和逐步代入四步;再把物不知数用两种方法各解一遍;最后做变式题,回查最容易错的地方:合并后忘了回代验算两个同余式。

必背

  1. CRT 两个前提缺一不可:模数两两互素、解限定在 0 ≤ x < N;答案要写成 x ≡ x₀ (mod N) 而不是单个数。
  2. 两两互素不能弱化成整体互素:6、10、15 三个数整体 gcd 为 1,但任意两个都不互素。
  3. CRT 逐步代入模板:参数化 → 代入下一式解模逆 → 再参数化,最终形式 x = N·u + x₀。
  4. 物不知数的解是 x ≡ 23 (mod 105);构造法基元 70、21、15,140 + 63 + 30 = 233,减 210 得 23。
  5. CRT 在密码学里是加速工具:RSA 解密分别在模 p、模 q 下算再合并,叫 RSA-CRT。
  6. 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。

顶部是 20 的 37 次方 mod 77,下面写 77 = 7 × 11,分成左右两路。左路模 7:20 ≡ −1,(−1) 的 37 次方 = −1 ≡ 6。右路模 11:20 ≡ −2,37 mod 10 = 7,(−2) 的 7 次方 = −128 ≡ 4。两路汇合到底部 x ≡ 48 (mod 77),验算 48 mod 7 = 6,48 mod 11 = 4

解法:

  1. 拆模数:77 = 7 × 11,两者互素,符合 CRT 前提。
  2. 模 7 这一路:20 ≡ 6 ≡ −1 (mod 7),故 20³⁷ ≡ (−1)³⁷ = −1 ≡ 6 (mod 7)。
  3. 模 11 这一路:20 ≡ 9 ≡ −2 (mod 11),φ(11) = 10,用欧拉定理降指数,37 mod 10 = 7,故 20³⁷ ≡ (−2)⁷ = −128;128 = 11 × 11 + 7,所以 −128 ≡ −7 ≡ 4 (mod 11)。
  4. 合并 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 ✓)。
  5. 设 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 的密钥生成和解密会直接调用本讲的四块零件。去之前把完整例题独立重做一遍,做到不看步骤能写全。

下一讲 →
Lab1 Lab1 智能合约入门:14 行代码上链,然后把每一分钱对上账

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。