问题
RSA 与 Diffie–Hellman 的安全性建立在两条经验断言上：大整数分解与模 p 离散对数在经典计算机上没有多项式时间算法。但 «没有» 从未被证明——连 «P ≠ NP» 这个前置问题都未解。本问的精确形态：在标准复杂度假设下，分解/离散对数是否 NP-中间（不在 P 内、也（可能）不是 NP-完全）？或至少给出 «任何算法都需 eΩ((log n)1/3) 步» 的下界？现状：最好的经典算法是亚指数的（数域筛法）；量子算法（Shor 1994）多项式求解——但 «困难性本身» 的任何无条件下界都为零。有趣的是，「判定」侧（素性测试）已被完全解决：素性 ∈ P（AKS 2002）—— «判定容易、构造难» 的分野正是问题的核心。
主要概念
证书与复杂度类
分解 ∈ NP ∩ coNP：合数性证书 = 一个非平凡因子（可直接验证）；素数性证书 = 普拉特证书（命题 1）——递归的 «p 素，因为存在 a 使 ap−1 ≡ 1 且每个 q | p−1 都过不了这个测试，且 q 素（递归）»。若分解 NP-完全，则 NP = coNP——这被视为 «分解不是 NP-完全» 的强证据。
亚指数算法谱系
二次筛 O(e(1+o(1))√(log n log log n))；数域筛 O(e((64/9)1/3+o(1)) (log n)1/3(log log n)2/3)——都基于 «光滑数的相关性»：找 B-光滑的 «关系» 拼出模平方根。离散对数在 ℤp* 上同谱系（指标计算法）；椭圆曲线群上无已知亚指数算法（这是 ECC 安全性的全部依据）。
主要命题与证明
命题 1（普拉特证书，完整证明） 素性 ∈ NP：对素数 p，存在长度 O(log²p) 的可验证证书。
证明 证书结构：对待测数 n，附上 a 与声明 «ord(a) = n−1»，以及 «n−1 的每个素因子 q 的素性证书»（递归）。验证：an−1 ≡ 1 (mod n) 且对每个 q | n−1 有 a(n−1)/q ≢ 1 (mod n)。正确性：设 d = ord(a)。条件一给 d | n−1；条件二对每个素因子 q 排除 d | (n−1)/q（否则该幂 ≡ 1），故 d = n−1。由拉格朗日定理 d | |(ℤ/nℤ)*| = φ(n)，故 n−1 ≤ φ(n) ≤ n−1，等号成立仅当 n 素（合数时 φ(n) ≤ n−2）。存在性：n 素时乘法群循环，取原根为 a。递归深度 ≤ log₂n（素因子链每次至少减半），总证书长度 O(log²n)，验证用快速模幂。□
命题 2（AKS 定理 2002，完整陈述） 素性 ∈ P：存在确定性多项式时间算法判定任意 n 是否素数（原始运行时间 Õ(log7.5n)，后续改进至 Õ(log6n)）。核心判据：n 素 ⟺ (x + a)n ≡ xn + a (mod n, xr − 1) 对足够多的 a 与某个小 r 成立—— «费马小定理的多项式版»，用 xr−1 截断控制验证成本。
命题 3（Pollard ρ 的复杂度，完整分析骨架） 分解 n 的 ρ 算法在 O(√p) 步内找到 n 的素因子 p（期望）——生日悖论：随机映射的 «碰撞» 出现在 √(群大小) 步内。Floyd 判圈使空间开销 O(1)。□
命题 4（困难性下界的现状，严格梗概） ①分解/离散对数不在 P 的任何相对化/黑盒下界已知（自然证明障碍与相对化障碍同样适用）；②已知最强无条件：分解需 Ω(log n) 步（平凡）；③若分解 NP-完全则 NP = coNP（由命题 1 的 coNP 侧 + 多项式归约的标准论证），主流复杂度观点视之为 «分解非 NP-完全» 的证据；④Shor 算法：量子计算机上 Õ((log n)³)—— «困难» 只在经典模型内有意义。
进展与文献
数域筛的谱系：Lenstra–Lenstra 编《The development of the number field sieve》与 Pomerance 的筛法综述；AKS 论文〈PRIMES is in P〉(Annals 2004)；Shor 1994。密码学侧的现状声明：RSA 安全性的 «证明» 形态是 «归约的失败» ——所有已知攻击都等价于分解，而 «分解难» 是经验命题。前沿的 «后量子» 转型（格密码）正基于此诊断：与其等一个 «困难性证明»（可能永远不来），不如换到 «最坏情况归约» 可用的数学结构上（格问题的最坏/平均联系是已证定理——Ajtai 1996）。本问因此是 «数论与计算复杂性» 的接壤线：数学侧给不出下界，复杂度侧给不出上界，工程侧在经验中航行。