32、亚指数时间离散对数与因式分解及更多环论知识

亚指数时间离散对数与因式分解及更多环论知识

亚指数时间离散对数与因式分解

在离散对数计算和整数因式分解算法的研究中，有许多实用的改进方法。

1. 降低失败概率

当我们设定 $\ell = 20$ 时，失败概率可降至百万分之一以下，且相对于算法 SEF，运行时间的增加几乎可以忽略不计。

2. 实用改进措施

2.1 更精确的平滑数密度估计

从算法角度来看，提高算法 SEDL 和 SEF 运行时间的简单方法是使用更精确的平滑数密度估计。定理 16.1 给出了平滑数密度的有效下界，但不够“紧密”，实际的平滑数密度会稍高一些。
有如下定理：
定理 16.7：设 $y$ 是 $x$ 的函数，对于某个 $\epsilon > 0$，有 $y = \Omega((\log x)^{1 + \epsilon})$ 且 $u := \frac{\log x}{\log y} \to \infty$（当 $x \to \infty$），则 $\Psi(y, x) = x \cdot \exp[(-1 + o(1))u \log u]$。

将此结果应用于算法 SEF 的分析，假设 $y = \exp[(\log n)^{1/2 + o(1)}]$，可改进不等式 (16.8)，得到 $E[T] \leq \exp[(1 + o(1)) \max{(1/2)(\log n / \log y) \log \log n + 2 \log y, 3 \log y}]$。若设定 $y := \exp[(1/2)(\log n \log \log n)^{1/2}]$，则 $E[T] \leq \ex