9.3 素数、因数分解与 RSA 数学边界
素数既是整数分解的基本构件，也出现在公钥密码和哈希表讨论中。但“用了质数”不自动带来安全或均匀性；算法性质取决于完整构造。
素数与算术基本定理
大于 1、正因数只有 1 和自身的整数称为素数。大于 1 的非素数称为合数。
算术基本定理：每个大于 1 的整数都能写成素数乘积，并且除因子顺序外分解唯一。
360=2³·3²·5唯一分解使 gcd、lcm 和约分可以按素因子指数理解，但实际求大整数因数分解可能很难。
试除与筛法
先排除 n<2。对其余整数判断是否为素数时，若有非平凡因子，至少有一个不超过 √n。因此可试除到平方根。
避免浮点平方根边界，可使用：
d <= n // d // positive integer division, d >= 2并先处理 2，再只试奇数。
若要找一段范围内全部素数，Eratosthenes 筛从小素数开始标记倍数，典型时间约 O(N log log N)、空间 O(N)。分段筛可降低大区间内存。
Python 3.8+ 的 isqrt 给出精确整数平方根。筛到素数 p 时，p² 之前的复合倍数已由更小素数标记，可从 p² 开始：
from math import isqrt
def primes_up_to(n):
if n < 2:
return []
prime = bytearray(b"\x01") * (n + 1)
prime[0] = prime[1] = 0
for p in range(2, isqrt(n) + 1):
if prime[p]:
for multiple in range(p * p, n + 1, p):
prime[multiple] = 0
return [p for p in range(2, n + 1) if prime[p]]
print(primes_up_to(20)) # [2, 3, 5, 7, 11, 13, 17, 19]
print(len(primes_up_to(100))) # 25这份实现为 0 到 n 分配标记数组，并另存输出列表；分段筛能缩小标记区间，但输出若全部保留，仍然占用空间。
试除适合小数，不适合密码规模。
素性测试不等于因数分解
素性测试回答“n 是否为素数”；因数分解要求给出合数的因子。前者存在多项式时间确定性算法，实践中也有高效概率测试；后者对一般大整数没有已知经典多项式时间算法。
Miller–Rabin 对奇数 n≥3 写出：
n-1=2^s d，d 为奇数对底数 1≤a<n，先算 x=a^d mod n。若 x 为 1 或 n-1，本轮通过；否则至多平方 s-1 次，期间出现 n-1 才通过。均未出现就得到合数见证。固定一个奇合数，每轮在上述范围独立均匀选底数，连续通过 k 轮的概率至多为 4^-k。这是“给定合数却通过”的概率界，不是“已经通过所以是合数”的后验概率。算法与界见 MIT 素性测试讲义。
例如 2047=23×89，且 2046=2×1023。底数 2 得到 2^1023 mod 2047=1，所以这一轮会通过；底数 3 得到 1565，既非 1 也非 2046，且没有后续平方轮数，于是证明它是合数。一个底数通过，先别急着给它发素数证书。
对固定机器整数范围，可以使用已知的一组确定底数得到确定判断；具体底数组合依赖数值上界，不能把 64 位规则照搬到任意大整数。
密码密钥生成应使用标准规定和成熟库，包括候选生成、随机源、额外检查与参数长度，不应自行拼接 Miller–Rabin。
RSA 的数学骨架
教学模型：
- 选择不同奇素数
p,q，实际密钥需满足标准的规模要求； n=pq；- 计算
λ(n)=lcm(p-1,q-1)； - 选择
3≤e<n使gcd(e,λ(n))=1； - 求
d≡e⁻¹ (mod λ(n))。
公钥包含 (n,e)，私钥包含 d 及常用 CRT 参数。基本运算：
c≡m^e (mod n)
m≡c^d (mod n)消息代表元取 0≤m<n，私有指数取正整数。正确性可分别模 p、q 证明：若 p|m，两边都为零；否则由 Fermat 定理和 ed≡1 (mod p-1) 得 m^(ed)≡m (mod p)。模 q 同理，再用 CRT 合并。这也覆盖与 n 不互质的消息，不能只套 Euler 定理就略过它们。
下面用 Python 3.8+ 穷举小模数的所有消息，检验原始 RSA 算术。这两个因子已经写在代码里，试除也很快，不能承担任何保密任务：
from math import gcd
p, q = 61, 53 # Tiny public teaching values, unsuitable for security.
n = p * q
lam = (p - 1) // gcd(p - 1, q - 1) * (q - 1)
e = 17
d = pow(e, -1, lam)
m = 65
c = pow(m, e, n)
print(n, lam, d, c, pow(c, d, n)) # 3233 780 413 2790 65
assert all(pow(pow(m, e, n), d, n) == m for m in range(n))教科书 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 的幂固定步长探测 (h+i·step) mod m 会访问 m/gcd(step,m) 个槽位；步长与容量互质时才遍历整表。质数容量让每个 1≤step<m 都满足这个条件。线性探测的步长恒为 1，对任何容量都能遍历整表，并不需要质数容量。探测覆盖范围也不等于键分布均匀。
用 Python 3 数一下被访问的槽位，就能看到容量为 8 时，步长 2 与步长 3 的差别：
from math import gcd
for m, step in [(8, 2), (8, 3), (7, 2)]:
visited = {(i * step) % m for i in range(m)}
assert len(visited) == m // gcd(m, step)
print(m, step, len(visited))
# 8 2 4
# 8 3 8
# 7 2 72 的幂容量能用掩码快速索引并方便倍增。若高低位经过良好混合，它完全可以表现良好；若只取低位，而键的低位规律强，就会聚集。
因此不能笼统说“质数一定碰撞少”。应：
- 遵循具体集合实现的容量策略；
- 使用有质量的哈希混合；
- 对攻击者可控键采用抗哈希洪泛措施；
- 通过负载因子和真实键分布压测。
密码哈希与哈希表散列的目标也不同，不能互换评价标准。
密码实现的最低边界
- 不自己实现 RSA 填充、素数生成或常数时间运算；
- 使用维护中的标准库和明确算法标识；
- 按当前标准选择密钥长度与签名/加密方案；
- 区分加密、签名和密钥交换；
- 设计密钥轮换、吊销和算法迁移；
- 通过测试向量与互操作验证实现。
数论解释算法为何成立，不能单独证明实现安全。
完成检查
- 用筛法列出 100 以内素数；
- 解释 Miller–Rabin 的“见证”和“概率素数”分别意味着什么；
- 用小素数手算 RSA 教学例子，并明确它不安全；
- 说明 OAEP/PSS 为什么不是可选装饰；
- 构造低位相同的键，比较直接掩码与混合后索引；
- 解释“能分解就能破 RSA”与“RSA 反演已证明等价于分解”的区别。