题解：P4718 【模板】Pollard-Rho

当 $N$ 有一个 $\sqrt N$ 左右的因子时, 可以判断:

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

事实上, 这个方程的非平凡因子并不少, 如果 $N$ 不形如 $p^r$, 即有两个相异素数 $P, Q$ 整除 $N$, 则可以构造出

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

然后我们考虑如下过程: 从 $\lceil \sqrt N \rceil$ 开始, 计算 $M$ 个值:

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

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

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

为什么 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 提升即可.

期望时间为

我们把分母记作 $\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$, 易得

此时复杂度为:

我们可以多选取一些 $(ax + b)^2 - N$ 在 $x \approx 0$ 处的取值, 这样会更容易找到 $u^2 \equiv v^2$.