Appearance
本章是初等数论与离散概率的应用篇：密码学（RSA 是数论集大成者）、伪随机数生成、算法平均复杂度分析（快速排序/桶排序/散列表）、随机算法（拉斯维加斯与蒙特卡罗）。
密码学（重点）
经典密码
| 密码 | 加密方式 | 特点 |
|---|---|---|
| 恺撒密码 | E(i) = (i+k) mod 26 | 移位密码，易破 |
| 线性同余密码 | E(i) = (ai+b) mod 26，a 与 26 互素 | 仿射密码 |
| 维吉利亚密码 | 密钥 k₁…kₙ，cⱼ = (iⱼ+kⱼ) mod 26 | 多表替换，分组密钥 |
RSA 公钥密码（核心考点）
密钥生成：
- 取两个大素数 p、q，n = pq，φ(n) = (p−1)(q−1)
- 选 w 与 φ(n) 互素（加密密钥，公开）
- 求 d = w⁻¹ mod φ(n)（解密密钥，保密）
加解密：
- 加密：c = mʷ mod n（m < n 为明文段）
- 解密：m = cᵈ mod n
正确性依据：欧拉定理 + 费马小定理（dw ≡ 1 mod φ(n) ⇒ m^(dw) ≡ m mod n）。
- 安全性：从公开的 n、w 求 d 需要分解 n（大整数分解困难）
- 模幂乘：把指数 b 写成二进制，反复平方取模，O(log b) 次乘法
例：p=43, q=59, n=2537, φ=2436, w=13, d=937。明文 VG(2106) → 密文 2106¹³ mod 2537 = 2321。
产生伪随机数（考点）
线性同余法
xₙ = (axₙ₋₁ + c) mod m，取 uₙ = xₙ/m 作为 U(0,1) 伪随机数。
- 序列质量取决于 m、a、c 的选择；m=2³¹−1, a=7⁵ 的乘同余法（c=0）周期达 2³¹−2
- 随机数与伪随机数：伪随机数是确定算法生成、看似随机的序列
离散分布伪随机数
- 逆变换法：产生 u~U(0,1)，按分布律累加概率确定 x（算法 13.1）
- 泊松分布：p₀=e⁻λ，pₖ₊₁=λpₖ/(k+1) 递推累加
- 二项分布：方法一按分布律累加；方法二 = n 个 0-1 变量之和（逐个模拟）
算法的平均复杂度分析（考点）
快速排序
- 平均时间 Tₙ 满足 Tₙ = (1/n)Σ(Tᵢ₋₁+Tₙ₋ᵢ) + O(n)，解得 O(n log n)
- 最坏情形（已排序输入）O(n²)
桶排序
[0,1) 上 n 个数分到 n 个桶，每桶内插入排序：平均 O(n)（输入均匀分布时）。
散列表（重点）
- 散列函数 h: U→{0,…,m−1}；冲突 = 两个关键码散列到同一位置
- 负载因子 α = n/m（已有 n 个数据）
- 链接法：冲突挂链表；插入/检索平均 O(1+α)
- 开地址法：线性搜索 h(K,i)=(h₁(K)+ic) mod m；双散列 h(K,i)=(h₁(K)+ih₂(K)) mod m；检索期望 O(1/(1−α))
与 哈希表-链地址法 互补阅读（那里有 C 实现）。
随机算法（考点）
分类（必背）
| 类型 | 特征 | 例 |
|---|---|---|
| 拉斯维加斯 | 结果总是正确，可能拒绝回答 | 随机快速排序 |
| 蒙特卡罗 | 可能给出错误结果（有错误概率） | 多项式恒零测试、素数测试 |
| 单侧错误 | 只可能把"是"说成"非"（或反之） | 素数测试 |
| 双侧错误 | 两类错误都可能 | — |
典型随机算法
- 随机快速排序：随机选轴值，平均 O(n log n) 与输入分布无关（拉斯维加斯）
- 多项式恒零测试：随机取点代入，非零则 p≢0；错误概率 ≤ d/|S|，重复 k 次降到 ≤ 2⁻ᵏ（单侧）
- 素数测试（Miller-Rabin 思想）：随机选 a，检查 a^(n−1) 及平方根链；合数被判为素数的概率 ≤ 1/2，重复 k 次错误率 ≤ 2⁻ᵏ（单侧）
费马小定理是素数测试的基础：若 n 为素数则 a^(n−1)≡1(mod n)；不满足即 n 是合数。
一句话总结
RSA = 素数 + φ 函数 + 模逆，加解密是模幂运算；伪随机数靠线性同余；平均复杂度分析把随机性带入递推；随机算法用"重复降低错误概率"换取效率。