题解：P4718 【模板】Pollard-Rho

· · 题解

请务必点开每一个隐藏栏.

:::warning[\textbf{\textsf{第零个大问题}}] 英文标点是为了与下标 0 混淆, 也是数学写作的通用习惯. 这不会在排版观感上对阅读造成障碍, 因此求管理员通过. :::

本篇题解, 介绍数域分解.

二次筛

:::error[\textbf{\textsf{小问题.}}\ 713\ \textbf{\textsf{是一个质数吗?}}] 不是, 它等于 23 \cdot 31. 注意力好的同学可以注意到

713 = 729 - 16 = 27^2 - 5^2 = (27 - 4) (27 + 4).

:::

:::info[\textsf{\textbf{这该如何推广?}}] 当 N 有一个 \sqrt N 左右的因子时, 可以判断:

(\lceil \sqrt N \rceil + K)^2 - N

是否是完全平方. 例如 \lceil \sqrt{713} \rceil = 27, 这就使得可以在 1 次尝试内得到结果. :::

但是这个方法不一定好用, 当 N 没有 \sqrt N 附近的因子可能还没有试除法来的好用.

我们发现, 上述过程只利用了 A^2 - B^2 = N, 而没有利用 A^2 - B^2 = cN 的情形, 也就是 A^2 \equiv B^2 \pmod N 的非平凡解, 这样 \gcd(A-B, N) 会是 N 的一个非平凡因子.

:::info[A^2 - B^2 = N\ \textbf{\textsf{的平凡解占比多吗?}}] 事实上, 这个方程的非平凡因子并不少, 如果 N 不形如 p^r, 即有两个相异素数 P, Q 整除 N, 则可以构造出

\begin{aligned} A \equiv B \pmod P, A \equiv -B \pmod Q; \\ A \equiv -B \pmod P, A \equiv B \pmod Q. \end{aligned}

这两个非平凡解, 相比于对应的平凡解, 个数是相等的. 而形如 P^3 Q^4 的 N 的非平凡解只会更多. 因此 A^2 \equiv B^2 \pmod N 有至少一半是非平凡解. :::

:::info[\textbf{\textsf{所以, 我们能导出什么样的算法?}}] 然后我们考虑如下过程: 从 \lceil \sqrt N \rceil 开始, 计算 M 个值:

F_K = (\lceil \sqrt N \rceil + K)^2 - N\ (K = 0, 1, \dots, M-1).

如果能找到一个非空子集 S \subset \{0, 1, \dots, M - 1\} 使得

\prod_{k \in S} F_k\ \text{是平方数},

那么我们就能找到 A^2 \equiv B^2 \pmod N, 进而找到 N 的一个非平凡因子. 这其实相当于异或线性基问题: 如果我们能把 F_K 全部分解成

F_K = \prod_{p} p^{\nu_p(F_k)},

则 \nu_p(F_k) \bmod 2\ (\forall p) 对应于一个 \mathbb F_2-空间上的向量, 进而只需判断这些向量是否线性相关. :::

:::success[\textbf{\textsf{实例验证}}\ N = 989] 用实例验证: 考虑 N = 989, 则 \lceil \sqrt N \rceil = 32, 则

\begin{aligned} F_1 = 100 = 2^2 \cdot 5^2 \end{aligned}

作为 \mathbb F_2-向量等于 0. 因此 10^2 \equiv 33^2 \pmod N \implies 23 \mid N. :::

但是最坏的情况下我们可能要很多个 F_K 才能找到线性相关的解法, 然后每个都试除就给出了比试除法还劣的复杂度. 但这种方法仍然有意义, 因为我们可以考虑限制 F_K 以把极慢的试除法淘汰掉.

我们发现所有素因子都小于一个阈值 P_{\max} 的数记好分解, 因为只需要试除 \dfrac{P_{\max}}{\log P_{\max}} 次就好, 甚至可以用 Erathothenes 筛获得更快的做法.

:::warning[\textbf{\textsf{第一个大问题: }}] 怎么判断那些 F_K 的满足其素因子全部小于 P_{\max}? :::

:::info[\textbf{\textsf{能否从 Eratosthenes 筛获得启发?}}] 为什么 Eratosthenes 筛很快? 因为 p 的倍数很有规律, 你可以直接一行循环模拟. 那么对于 F_K 呢? 这相当于解 X^2 - N = p A, 也就是 X^2 \equiv N \pmod p. 这是一个典型的二次剩余问题.

现在考虑这样的方法: 把 F_K 一列列开, 并复制一个副本 F^c_K. 现在对于每一个 p^r < P_{\max}, 将位置 S = \{ K : p^r \mid F_K \} 中的数 K 对应的 F^c_K 除以 p. 这样, 只需要解决 F_K \equiv N \pmod {p^r} 何时成立. Cipolla 算法求出一个 \operatorname{mod} p 意义下的解, 并 Hensel 提升即可. :::

:::success[\textbf{\textsf{实例验证}}\ N = 87\ 463] 假设 P_{\max} = 30, 经过上面的筛选过程, 我们得到

\begin{aligned} F_{-30} = -17\ 238 = (-1) \cdot 2 \cdot 3 \cdot 13^2 \cdot 17, \\ F_{-17} = -10\ 179 = (-1) \cdot 3 \cdot 13 \cdot 29, \\ F_1 = 153 = 3 \cdot 17, \\ F_4 = 1\ 938 = 2 \cdot 3 \cdot 17 \cdot 19, \\ F_{12} = 6\ 786 = 2 \cdot 3^2 \cdot 13 \cdot 29, \\ F_{21} = 12\ 393 = 3^6 \cdot 17. \end{aligned}

用线性基算法可以发现 F_{-30} F_{-17} F_1 F_{12} 是一个平方数, 得到 A^2 \equiv B^2 \pmod N 的非平凡解:

\begin{aligned} A = 265 \cdot 278 \cdot 296 \cdot 307 \equiv 34757 \pmod N, \\ B = \sqrt{(265^2 - N) (278^2 - N) (296^2 - N) (307^2 - N)} \equiv 28052 \pmod N. \end{aligned}

进而导出 149 \mid N. :::

:::info[\textbf{\textsf{时间复杂度分析}}] 期望时间为

\dfrac{\pi(P_{\max}) \log \log P_{\max} \sqrt N}{|\{D : 1 \le D \le \sqrt N, D\ \text{的素因子全都}\ \lt P_{\max}\}|}.

我们把分母记作 \psi(\sqrt N, P_{\max}). 假定 P_{\max} = N^{1/2u}, 则 \pi(P_{\max}) \log \log P_{\max} \approx P_{\max}, \dfrac{\sqrt N}{\psi(\sqrt N, P_{\max})} \approx u^u (这分别是素数定理稍微保守一点的估计和 K. Dickman 的数论成果), 进而我们只需最小化 N^{1/2u} u^u, 易得

u \sim \sqrt{ \dfrac{\log N}{\log \log N} },

此时复杂度为:

T(N) \sim \exp \Big((1 + \mathrm o(1)) \cdot \sqrt{\log N \log \log N} \Big).

:::

:::info[\textbf{\textsf{多个二次多项式的优化}}] 我们可以多选取一些 (ax + b)^2 - N 在 x \approx 0 处的取值, 这样会更容易找到 u^2 \equiv v^2. :::