Shor 算法深入：数论基础、QFT 与 RSA 威胁量化

如果知道某个 a 关于 N 的「阶」r（最小正整数使 a^r ≡ 1 mod N）：
  a^r - 1 = (a^(r/2) - 1)(a^(r/2) + 1) ≡ 0 (mod N)
  → 若 r 偶数且 a^(r/2) ≢ ±1 (mod N)：
    gcd(a^(r/2) - 1, N) 与 gcd(a^(r/2) + 1, N) 是 N 的非平凡因数！

例：N=21，取 a=2，阶 r=12（2^12 ≡ 1 mod 21）
  2^6 = 64 ≡ 1 mod 21，64 ≢ ±1
  gcd(64-1, 21) = gcd(63, 21) = 21？不行
  → 换 a 再试（随机选 a，成功概率 ≥ 1/2）

1. 随机选 a（1 < a < N）
2. 求 gcd(a, N)：若 > 1 → 已找到因数，结束
3. 用量子电路求 a 的阶 r
4. r 奇数或 a^(r/2) ≡ ±1 → 换 a 重试
5. 否则 gcd(a^(r/2) ± 1, N) → 得因数

输入：整数 N（合数）、a（与 N 互素）
输出：最小正整数 r，使得 a^r ≡ 1 (mod N)

- 暴力：试 r=1,2,3,... → 指数时间
- 最优经典（数域筛）：次指数时间（e^((log N)^(1/3))）
- 求阶属于「无已知多项式经典算法」的问题族
- 量子：多项式时间（Shor）→ 求阶是「量子优势」的经典候选

经典：一次试一个 r（串行搜索）
量子：把「所有可能的 r 对应的函数值」编码进叠加态
   → 一次操作同时「探测」所有 r
   → QFT 把叠加「干涉」出周期 r

函数 f(x) = a^x mod N 是周期的，周期 = r：
  a^0, a^1, ..., a^(r-1) 循环
→ 求阶 = 找 f 的周期
→ 量子算法：叠加态里放大量 x → QFT 提取周期

寄存器 1：控制寄存器（2n 个量子比特，n = N 的位数）
  初始化均匀叠加：|0⟩ → Σ|x⟩

寄存器 2：工作寄存器（n 个量子比特）
  初始化 |1⟩，存储 a^x mod N 的结果

电路核心操作：
  U_a: |x⟩|y⟩ → |x⟩|y · a^x mod N⟩
  → 对叠加中的每个 x 同时计算 a^x mod N

a^x mod N 拆成「受控模乘法」的级联：
  a^x = a^(x0·2^0 + x1·2^1 + ... + xm·2^m)
  → 每步 = 受控乘 a^(2^k) mod N

电路深度：
  模乘法用「模加法 + 移位」实现（量子加法器）
  总门数约 O(n³)，n = 比特数
  → 这是 Shor 电路里「最贵」的部分

- 需要可逆：量子计算不可「丢弃」信息
- 模乘法电路：加法器 + 比较器 + 减法器的可逆组合
- 使用 ancilla（辅助比特）做临时存储
- 电路深度与 n³ 成正比 → 大 n 的门数可观

QFT 的作用：
  输入：叠加态 Σ|x⟩（含周期性分布）
  输出：傅里叶基下的分布（峰值在「周期对应的频率」）
  → 测量得到与周期 r 相关的值

数学本质：
  QFT 把 |x⟩ → (1/√N) Σ_y ω^(xy)|y⟩
  （ω = e^(2πi/N)，相当于 DFT 的量子版本）

QFT 由 H + 受控相位门组成：
  H on 第 k 位 + C-R_z(π/2^k) 级联
  深度 O(n²)，n = 比特数
  → 相比模幂的 O(n³)，QFT 便宜得多

- 相位估计的核心：把「酉算符的本征相位」映射到可测量位
- Shor 里：a^x mod N 的「循环」在 QFT 后出现尖峰
- 尖峰位置 ≈ m/r（m 与 r 相关）→ 下一步用连分数提取 r

经典 FFT：输入 N 个数字，输出 N 个频率分量（O(N log N)）
量子 QFT：输入叠加态，一次操作完成变换（O((log N)²) 门）
  → 指数「加速」来自把数据放进叠加态 + 一次变换

QPE 的问题：
  给定酉算符 U 和本征态 |u⟩（U|u⟩ = e^(2πiφ)|u⟩）
  估计相位 φ（0 ≤ φ < 1）

Shor 里的用法：
  U = 乘 a 的算符（U|x⟩ = |a·x mod N⟩）
  本征态含「a^x mod N 的循环」
  → 相位 φ ≈ m/r → 由 φ 恢复 r

控制寄存器（t 个比特）：|0⟩ ⊗^t → 叠加
工作寄存器：|u⟩（本征态）
受控-U^(2^k) 级联：把相位信息「写进」控制寄存器的相对相位
最后 QFT⁻¹：把相位还原成可读二进制数
→ 测量得到 2^t · φ 的近似

- t 个控制比特 → 相位精度约 1/2^t
- t = 2n + 1 位控制比特 → 以高概率得到精确的 m/r
- 测量结果 m ≈ 2^(2n+1) · φ → 求 m/(2^(2n+1)) 的连分数收敛

- 相位估计精度不够 → 连分数提取不到准确 r
- 控制比特多 = 电路宽 = 资源成本
- 权衡：2n+1 是经典理论推荐（成功率高、资源可控）

1. 求连分数展开：m / 2^(2n+1)
   的收敛分数 p/q 中，找 q = 阶 r（成功的那个）
2. 检查：a^r ≡ 1 mod N？是 → r 正确
3. 由 r 得因数：
   r 偶且 a^(r/2) ≢ ±1 → gcd(a^(r/2) ± 1, N)
4. 失败 → 换 a 重试（成功概率 ≥ 1/2）

# 连分数提取阶（示意）
def order_from_measurement(m, M, a, N):
    for p, q in continued_fraction(m, M):   # 连分数收敛序列
        if pow(a, q, N) == 1:               # 验证是阶
            return q
    return None

# 由阶得因数
def factor_from_order(a, r, N):
    if r % 2 == 0:
        g1 = math.gcd(pow(a, r//2, N) - 1, N)
        g2 = math.gcd(pow(a, r//2, N) + 1, N)
        for g in (g1, g2):
            if 1 < g < N: return g
    return None

随机选 a：
  - gcd(a, N) > 1 → 直接找到因数（~小概率）
  - 阶提取成功 → 需要 r 偶且 a^(r/2) ≢ ±1
  - 随机 a 的成功概率 ≥ 1/2 → 几次重试就够
→ 期望 O(1) 次重复，整体多项式

- 连分数：O(log N) 步，几乎免费
- 验证 a^q ≡ 1 mod N：快速幂 O(log q)，也便宜
- 经典部分不是瓶颈——量子电路才是

电路规模（门数）：O(n³)  （模幂 O(n³) + QFT O(n²) + 其他）
量子比特数：     O(n)    （控制 2n + 工作 n + 辅助）
经典后处理：    O(n²)     （连分数 + 幂运算）
→ 总时间多项式：O(n³ log n log log n)

经典数域筛（GNFS）：次指数 L(n) = exp(O(n^(1/3) log²/³ n))
  n 增大 → 经典时间超多项式增长
量子 Shor：多项式 O(n³)
  n 增大 → 时间多项式增长

关键差距：n=2048 位 RSA：
  经典：百万年级（推测）
  量子：千万级门（当前估计，仍难但原则可行）

- 多项式：输入翻倍 → 时间翻常数倍
- 次指数/指数：输入翻倍 → 时间暴涨
→ 大 n 下两者拉开数量级差距
→ 这就是「量子威胁」的技术根源

- 上述是「逻辑量子比特」：还需大量物理比特做纠错
  （表面码每个逻辑比特 × 数十~数百物理比特）
- T 门在容错架构里极贵（需要魔术态蒸馏）
- 当前记录：分解的最大数远小于 RSA（如 N=21 已完整演示）
- 实验路线：2030 年代容错原型 → 2040 年代威胁现实化（推测）

- 2048 位 RSA：目前「工程不可行」但「原则可行」
- 短期威胁：低（容错机器还没到）
- 长期威胁：确定性（多项式算法 + 硬件进展）
- 结论：现在就该规划「后量子迁移」——等威胁落地再动就晚了

- 优化模幂电路（减少 T 门/比特）
- 用「近似 QFT / 并行化」降深度
- 专用硬件架构（针对 Shor 电路）

阶段 1：演示性实现（N=15, 21, 35...）——已大量完成
  用「已知周期」的简化电路（非通用求阶）
阶段 2：通用求阶电路的小规模验证——进行中
阶段 3：容错机器上运行大 RSA——远期（2030s+）

- 已分解的最大 N 很小（两位/三位数）
- 多数实验「利用已知答案简化电路」（作弊式）
- 真正的「通用 Shor」需要容错（噪声下模幂电路太长）
- 这是「逻辑门精度 + 纠错」工程问题，不是算法问题

- 只针对「特定问题族」（求阶/因数分解）
- 需要大规模容错机器（NISQ 跑不了大 Shor）
- 多项式但常数不小：电路工程复杂
- 量子资源估算仍有不确定性（降噪/架构进展在变）

- 只要 Shor「原则可行」→ RSA/ECC 长期不安全（无论硬件多快）
- 后量子密码（格/编码/MQ）——见 [[quantum-post-quantum-cryptography]]
- 迁移窗口：数据有保密期（先记录的密文，等量子解密）
  → 「现在记录、以后解密」是现实威胁