31、次指数时间离散对数与因式分解算法

次指数时间离散对数与因式分解算法

1. 平滑数

在数论领域，平滑数是一个重要的概念。若 $y$ 为非负实数，$m$ 为正整数，当 $m$ 的所有质因数都不大于 $y$ 时，称 $m$ 为 $y$ - 平滑数。对于 $0 ≤ y ≤ x$，定义 $\Psi(y, x)$ 为不超过 $x$ 的 $y$ - 平滑整数的数量。下面的定理给出了 $\Psi(y, x)$ 的一个下界，这在后续离散对数和因式分解算法的分析中起着关键作用。

定理：设 $y$ 是 $x$ 的函数，当 $x → ∞$ 时，满足 $\frac{y}{\log x} → ∞$ 且 $u := \frac{\log x}{\log y} → ∞$，则有 $\Psi(y, x) ≥ x · \exp[(−1 + o(1))u \log \log x]$。

证明思路：
- 首先，将 $u$ 表示为 $u = ⌊u⌋ + δ$，其中 $0 ≤ δ < 1$。
- 把不超过 $y$ 的质数分成两个集合：集合 $V$ 包含不超过 $y^{\delta/2}$ 的“非常小”的质数，以及整数 $1$；集合 $W$ 包含大于 $y^{\delta/2}$ 但不超过 $y$ 的质数。
- 根据伯特兰假设，存在常数 $C > 0$，对于足够大的 $y$，有 $|W| ≥ \frac{Cy}{\log y}$。由于 $\frac{y}{\log x} → ∞$，对于足够大的 $x$，可得 $|W| ≥ 2⌊u⌋$。
- 为了得到下界，我们考虑那些由 $⌊u⌋$ 个不同的 $W$ 中的元素与一个 $V$ 中的元素相乘得到的