Sherfiter's wiki for fun

第 9 章 · 数论与 RSA

数论研究整数的性质(整除、余数、素数),曾被认为是「最无用的数学」( Hardy 的傲慢),直到 1977 年 RSA 问世:你每天打开的 HTTPS,钥匙就是本章的每一条定理。这是全课程「变现」最直接的一章:整除 → 模运算 → 欧几里得 → 费马 → RSA,一条直线通到互联网的地基。

9.1 整除与欧几里得算法

整除:a | b 表示存在整数 k 使 b = ka。核心事实:带余除法:任意整数 a = qn + r(0 ≤ r < n,q 商 r 余),余数 r = a mod n 是唯一确定的(第 1 章同余关系的操作基础)。

最大公约数 gcd(a, b):同时整除两者的最大正整数。欧几里得算法(2300 年前的算法,仍在服役):

gcd(a, b) = gcd(b, a mod b),gcd(a, 0) = a
gcd(48, 18):48 = 2×18 + 12 → gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6

正确性:48 与 18 的公约数集合 = 18 与 12 的公约数集合(余数 = a − qb,能整除 a、b 的必能整除余数,反之亦然)。复杂度 O(log min(a,b))(斐波那契相邻项是最坏情况,拉美,数据结构课第 1 章)。扩展欧几里得:顺路算出 x、y 使 ax + by = gcd(a,b)——「最大公约数能表示成两数的整系数组合」(Bézout 定理),它是求模逆元的钥匙(9.3)。

9.2 模运算与同余

同余:a ≡ b (mod n) ⟺ n | (a − b) ⟺ a、b 除以 n 余数相同。同余的加法和乘法可以放心「先算再取余」或「先取余再算」(第 1 章验证过的等价关系 + 运算封闭):

(a mod n)+(b mod n)≡a+b(modn)(a \bmod n) + (b \bmod n) \equiv a + b \pmod n

这就是「时钟算术」,也是所有大数运算的降维术:计算 3¹⁰⁰⁰ mod 7 不需要真的算 3¹⁰⁰⁰,一路取余(甚至反复平方,把 1000 次乘法压到 log 次,数据结构课第 1 章 O(log n) 的又一次现身)。

模逆元:b 的模 n 逆元 b⁻¹ 满足 b·b⁻¹ ≡ 1 (mod n)。存在条件:gcd(b, n) = 1(互素)。求法:扩展欧几里得解 bx + ny = 1,则 x ≡ b⁻¹ (mod n)。例:5 的 mod 7 逆元是 3(5×3 = 15 ≡ 1)。除法在模运算里 = 乘逆元,这一步把「整数算术」升级成「域」(第 8 章:加减乘除俱全的代数结构),椭圆曲线密码、纠错码全在这片地基上。

9.3 费马小定理与欧拉定理

费马小定理:p 素数且 p ∤ a,则 a^(p−1) ≡ 1 (mod p)。第 8 章的证明一句话:模 p 乘法群 {1..p−1} 是 p−1 阶群,a 的倍数 1a, 2a, …, (p−1)a 是全群的重新排列,乘起来 ≡ (p−1)! ≡ 双方同乘 a⁻¹ 即得。群论的复利在此兑现。

欧拉定理(推广到合数):a 与 n 互素,则 a^φ(n) ≡ 1 (mod n),其中欧拉函数 φ(n) = 1..n 中与 n 互素的个数。φ 的计算(第 5 章容斥的成果):φ(p) = p − 1(素数);φ(pq) = (p−1)(q−1)( pq 的互素 = 「不是 p 的倍数」且「不是 q 的倍数」,容斥: pq − q − p + 1)。n = 15:φ(15) = 8(1, 2, 4, 7, 8, 11, 13, 14)。欧拉定理是 RSA 解密的直接依据。

9.4 RSA:一条定理变成一个帝国

RSA(Rivest-Shamir-Adleman, 1977)的完整流程,每一步挂上本章的定理:

① 选两个大素数 p、q(比如各 1024 位)     ← 素性测试(Miller-Rabin,概率算法)
② n = pq,φ(n) = (p−1)(q−1)             ← 欧拉函数
③ 选 e 与 φ(n) 互素(常取 65537)         ← 公钥的一部分
④ 求 d ≡ e⁻¹ (mod φ(n))                ← 扩展欧几里得(9.2)
⑤ 公钥 (n, e) 公布,私钥 d 保密
⑥ 加密:c = mᵉ mod n                     ← m 是消息的数字编码
⑦ 解密:m = cᵈ mod n

为什么解密能还原?cᵈ = m^(ed),而 ed ≡ 1 (mod φ(n)) 意味着 ed = kφ(n) + 1,由欧拉定理 m^(kφ(n)+1) = (m^φ(n))^k · m ≡ 1^k · m = m (mod n)。∎ 一行定理证明,全世界 HTTPS 的合法性。

安全性依赖:已知 n = pq 求 φ(n) = (p−1)(q−1) 需要分解 n;大数分解没有已知多项式算法(当前纪录是几百位十进制数,1024 位 RSA 已淘汰,2048 位是现行底线)。「乘法容易、分解难」的不对称性 = 公钥密码的存在前提。同族算法:Diffie-Hellman(离散对数难)、ECC(椭圆曲线上的离散对数,密钥更短)。三者在量子计算(Shor 算法)面前集体脆弱,后量子密码(NTRU、格密码)正在接班——这条战线至今活跃。

9.5 素数:分布与判定

素数是数论的「原子」。三个事实:

  • 素数有无穷多(Euclid,第 4 章的证明);分布稀疏但规律:素数定理说 n 附近密度约 1/ln n,「1024 位附近随便抓个奇数,试几百次就能撞见素数」——RSA 生成密钥就这么简单;
  • 判定素数:试除到 √n 太慢;Miller-Rabin 概率判定(误判率 < 4^(−k),工业标准),AKS 是确定多项式(2002 年,理论里程碑);
  • 分解与判定是两回事:判定一个数是不是素数很快,把它拆开很难。RSA 恰好站在这条不对称的缝隙里。

常见错误

  • 模运算直接除。「除以 b」必须换成「乘 b⁻¹」,而且 b⁻¹ 存在需要互素;漏查互素,解密直接出错。
  • φ(pq) 记成 pq−1。是 (p−1)(q−1);φ(15) = 8 不是 14,算错则 ed ≢ 1,解密得出垃圾。
  • 欧拉定理忘了互素前提。a 与 n 不互素时定理失效(RSA 的消息 m 与 n 不互素时的补救由 CRT 处理,实现细节);安全实现交给标准库,手搓要有这个意识。
  • 同余式两边约分。6·2 ≡ 6·9 (mod 42) 但 2 ≢ 9(6 与 42 不互素,消去非法);消去法要求「与模数互素的因子」。

练习

  1. 手算:用扩展欧几里得求 7 的 mod 26 逆元(仿射密码解密的实际一步),写出每轮的商和余数。
  2. 手算:用反复平方算 3⁶⁴⁴ mod 645(经典教学数字),写出每一步的平方与取余。
  3. 动手:实现一个迷你 RSA(p、q 取 100 以内素数,用 Python 不限):生成密钥、加密一个数、解密还原;再用 p = q 的「错误参数」跑一遍,观察为什么要求 p ≠ q。
  4. 思考:RSA 的安全 = 大数分解难。若量子计算机跑 Shor 算法,分解变成多项式时间。结合第 8 章(群的代数结构)解释:Shor 把「分解问题」归约到「求周期」,而周期在群语言里就是「元素的阶」——为什么「知道阶」就能分解?
豫ICP备2026027944号