9.3 素数、因数分解与 RSA 数学边界
安全要塞送来一把基于大整数的锁，塔里的任务不是赞叹质数，而是说明哪些计算困难支撑了它。
素数既是整数分解的基本构件，也出现在公钥密码和哈希表讨论中。但“用了质数”不自动带来安全或均匀性；算法性质取决于完整构造。
素数与算术基本定理
大于 1、正因数只有 1 和自身的整数称为素数。大于 1 的非素数称为合数。
算术基本定理：每个大于 1 的整数都能写成素数乘积，并且除因子顺序外分解唯一。
360=2³·3²·5唯一分解使 gcd、lcm 和约分可以按素因子指数理解，但实际求大整数因数分解可能很难。
试除与筛法
判断 n 是否为素数，若有非平凡因子，至少有一个不超过 √n。因此可试除到平方根。
避免浮点平方根边界，可使用：
d≤n/d并先处理 2，再只试奇数。
若要找一段范围内全部素数，Eratosthenes 筛从小素数开始标记倍数，典型时间约 O(N log log N)、空间 O(N)。分段筛可降低大区间内存。
试除适合小数，不适合密码规模。
素性测试不等于因数分解
素性测试回答“n 是否为素数”；因数分解要求给出合数的因子。前者存在多项式时间确定性算法，实践中也有高效概率测试；后者对一般大整数没有已知经典多项式时间算法。
Miller–Rabin 把奇数写为：
n-1=2^s d，d 为奇数然后对选定底数检查强伪素数条件。发现见证即可证明合数；通过若干随机底数则得到“概率素数”结论，错误概率随独立轮数降低。
对固定机器整数范围，可以使用已知的一组确定底数得到确定判断；具体底数组合依赖数值上界，不能把 64 位规则照搬到任意大整数。
密码密钥生成应使用标准规定和成熟库，包括候选生成、随机源、额外检查与参数长度，不应自行拼接 Miller–Rabin。
RSA 的数学骨架
教学模型：
- 选择不同大素数
p,q； n=pq；- 计算
λ(n)=lcm(p-1,q-1)或相应规范参数； - 选择
e使gcd(e,λ(n))=1； - 求
d≡e⁻¹ (mod λ(n))。
公钥包含 (n,e)，私钥包含 d 及常用 CRT 参数。基本运算：
c≡m^e (mod n)
m≡c^d (mod n)正确性来自指数同余，并可分别在模 p、模 q 下证明后用 CRT 合并。
教科书 RSA 不能直接使用
裸的 m^e mod n 是确定性的，不提供现代加密所需的语义安全，也容易受结构性和选择密文攻击。标准方案为基本 RSA 运算定义编码：
- 加密使用 RSAES-OAEP 等方案；
- 签名使用 RSASSA-PSS 等方案；
- 实际大数据通常使用混合加密，RSA 只封装随机对称密钥。
加密与签名不是“私钥加密/公钥解密”的同一个接口翻转。二者安全目标和编码不同。
RSA 安全也不应表述成已经证明“等价于因数分解困难”。高效分解 n 会泄露私钥，但一般 RSA 反演与因数分解的精确等价并未作为通用结论建立。安全判断依赖 RSA 问题、编码方案、密钥长度、实现和攻击模型。
量子 Shor 算法会在足够大的容错量子计算机上威胁 RSA；迁移策略已在第 8 卷密码学章节讨论。
哈希表容量：质数不是魔法
槽位映射常见两类：
index=floorMod(hash,m)
index=mixedHash & (m-1)，当 m 为 2 的幂质数模数可避免某些输入步长与表长共享因子导致的短周期，尤其在线性探测或简单多项式哈希中有用。但分布是否均匀由哈希函数、键分布、取位方式和冲突策略共同决定。
2 的幂容量能用掩码快速索引并方便倍增。若高低位经过良好混合，它完全可以表现良好；若只取低位，而键的低位规律强，就会聚集。
因此不能笼统说“质数一定碰撞少”。应：
- 遵循具体集合实现的容量策略；
- 使用有质量的哈希混合；
- 对攻击者可控键采用抗哈希洪泛措施；
- 通过负载因子和真实键分布压测。
密码哈希与哈希表散列的目标也不同，不能互换评价标准。
密码实现的最低边界
- 不自己实现 RSA 填充、素数生成或常数时间运算；
- 使用维护中的标准库和明确算法标识；
- 按当前标准选择密钥长度与签名/加密方案；
- 区分加密、签名和密钥交换；
- 设计密钥轮换、吊销和算法迁移；
- 通过测试向量与互操作验证实现。
数论解释算法为何成立，不能单独证明实现安全。
完成检查
- 用筛法列出 100 以内素数；
- 解释 Miller–Rabin 的“见证”和“概率素数”分别意味着什么；
- 用小素数手算 RSA 教学例子，并明确它不安全；
- 说明 OAEP/PSS 为什么不是可选装饰；
- 构造低位相同的键，比较直接掩码与混合后索引；
- 解释“能分解就能破 RSA”与“RSA 反演已证明等价于分解”的区别。