3. 因数分解的经典困难性
Shor算法之所以在密码学上具有颠覆性意义，是因为它把大整数分解从"经典计算机上已知没有多项式时间算法"的问题，变成了量子计算机上可多项式时间求解的问题。要真正理解这一冲击，必须先看清经典算法究竟"难"在哪里：不是难在写不出分解程序，而是难在随着整数位数增长，已知最好算法的运行时间增长得太快。本节沿着试除法、费马分解、二次筛法、数域筛法这条演进线索，说明经典困难性的来源，以及RSA安全性究竟依赖什么假设。
一、问题规模用什么衡量
讨论困难性前先约定度量方式。设待分解整数为 N，其二进制位数为 n = log₂N。算法复杂度通常写成关于 n 的函数，而不是关于 N 的函数。例如"枚举到 √N"写成 2^(n/2)，这是关于 n 的指数级，而不是多项式级。RSA-2048 的 N 有 2048 位，约 617 个十进制数字，这个量级决定了任何指数级方法都不可行。
二、试除法：最直观的指数级方法
试除法从 2 开始，依次用每个整数（实际只需素数）去除 N，直到找到因子或试到 √N。若 N 是合数且最小素因子为 p，则最多试到 p 即可成功。它的代价完全由最小素因子决定：如果 N 恰好是两个接近的大素数之积，最小素因子约为 √N，试除次数约为 √N = 2^(n/2)。
试除法有一个重要特性：它对"小因子"极其高效。若 N 含有一个 20 位的素因子，试除到 2²⁰ 量级即可分解。因此 RSA 的安全性要求两个素因子 p、q 都足够大且长度接近，避免出现小因子被轻易试出。这也解释了为什么实际生成 RSA 密钥时要检查 p、q 的位数并保证 |p−q| 不太小。
三、费马分解：针对"因子接近"的补刀
费马分解利用了平方差恒等式。若 N = a² − b²，则 N = (a+b)(a−b)。算法从 a = ⌈√N⌉ 开始，计算 a² − N，判断它是否为完全平方数；若不是则 a 加一继续。当 a 取到 (p+q)/2 时，a² − N 恰为 ((p−q)/2)²，分解成功。
它的迭代次数约为 (p+q)/2 − √N，当 p、q 非常接近时这个值很小，费马分解极快；但当 p、q 差距大时，迭代次数迅速膨胀，退化为接近 √N 量级。因此费马分解与试除法形成互补：试除法怕大因子，费马分解怕因子差距大。RSA 密钥生成必须同时避开这两种极端，即 p、q 既不能太小，也不能太接近。
四、二次筛法：从"逐个试"到"批量筛"
二次筛法（Quadratic Sieve, QS）的思路与试除法完全不同。它不直接找因子，而是寻找满足 x² ≡ y² (mod N) 且 x ≠ ±y (mod N) 的一对整数，此时 gcd(x−y, N) 就是 N 的一个非平凡因子。为构造这样的同余式，QS 在 √N 附近取一系列 x，计算 Q(x) = x² − N，并筛选出那些在某个小素数集合（因子基）上完全分解的"光滑数"。收集足够多的光滑关系后，通过模 2 线性代数求出它们的乘积组合，使指数全为偶数，从而得到平方同余。
QS 的复杂度是亚指数的，形如 L_N[1/2, c] = exp(c·(ln N)^(1/2)·(ln ln N)^(1/2))。它比试除法的 2^(n/2) 好得多，但随 N 增大仍增长很快，实际适用于约 100 位十进制以内的整数。历史上 RSA-129（129 位十进制）就是用 QS 在 1994 年分解的。
五、数域筛法：当前通用分解的顶峰
数域筛法（Number Field Sieve, NFS）把 QS 的"在整数中筛光滑数"推广到"在代数数域中筛光滑元素"，通过两个域（有理数域与一个代数数域）之间的同态映射构造平方同余。它的复杂度进一步降为 L_N[1/3, c]，指数中的 (ln N)^(1/3) 比 QS 的 (ln N)^(1/2) 增长更慢，因此在大数上优势明显。NFS 是当前已知最快的通用分解算法，RSA-250（250 位十进制）等挑战数就是用它完成的。
但"最快"不等于"够快"。以 RSA-2048 为例，用 NFS 分解所需的运算量估计在 2^110 量级以上，远超任何现有经典计算机的可行范围。这正是 RSA 安全性的核心：RSA 的安全性并不依赖"分解问题无解"，而是依赖"在目标位数下，已知经典算法所需时间远超现实可承受范围"。
六、RSA 安全性依赖什么
综合来看，RSA 的安全性建立在以下假设之上：
- 大整数分解困难假设：在 N 足够大（如 2048 位）且 p、q 选取得当时，没有已知经典算法能在可行时间内分解 N。
- 参数选取约束：p、q 必须足够大、长度接近但差距不能过小，以同时抵御试除法、费马分解和 Pollard rho 等特殊方法。
- 算法没有突破：NFS 的亚指数复杂度是当前最好结果，尚未出现多项式时间经典算法。
七、小结：困难性的本质
从试除法到数域筛法，经典算法的演进不断降低复杂度指数，但始终停留在亚指数级别，没有跨入多项式时间。试除法暴露了"小因子"和"因子接近"两类弱点，费马分解补上了因子接近这一刀，QS 和 NFS 则代表了通用方法的最优水平。RSA 的安全性正是建立在这一"亚指数但非多项式"的鸿沟之上。理解这条演进线，才能准确判断 Shor 算法带来的威胁边界：它不是让分解"更快一点"，而是把问题从亚指数直接拉进多项式时间，这是性质上的跃迁。