Pollard Rho 小记

_HL_ · 2022-10-01 15:51:23 · 题解

序

对于 Pollard Rho 算法流程和卡常技巧其他题解已经讲得很详细了，但其中笔者在学习时遇到以下问题：

1. 复杂度正确性？

2. 为何要用那个 Pollard 伪随机数列而非 mt19937 直接随一个？

3. 怎么想到的这个算法？

这些现有题解并未较完整的解答，本文将更完整的介绍。

通过对这些问题的理解，可以加深读者对于 Pollard Rho 算法正确性的信任，同时可以在背板子的时候明白每步在干什么，避免背了就忘的问题。

问题引入

考虑我们随了一个可重集 X=\{x_i\} ，x_i 的值域为 [0,n-1] (当然，整数)，我们记 y_i=(x_i\mod p)，于是我们得到了另一个可重集 Y=\{y_i\} 值域是 [0,p-1] 。

由生日悖论我们知道，当 |Y|>\sqrt p 时，Y 中基本上一定有至少一个数对 (y_i,y_j) 相等，设这样有至少一个数对相等的概率为 P_1 , 生日悖论告诉我们 P_1=1-\epsilon ， 即非常接近 1 。

所以 X 中有同样 P_1 的概率有至少一个数对 (x_i,x_j) ，满足 x_i\equiv x_j\pmod p。

考虑 x_i=x_j 的情况，出现这种情况的概率 P_2 是极小的 , 而剩下的 x_i\ne x_j 的情况，有 p|(|x_i-x_j|)。

“P_2 极小” 这个结论易于理解，即 n 个里选 k 个 ，k\le \sqrt p\le n^{\frac{1}{4}} ，能选出两个相同的数概率很小。具体证明大概挺数数的，读者有兴趣可以自己推一推，不是本文重点。

这说明什么？这说明我们只需要找 k(k\le \sqrt p\le n^{\frac{1}{4}}) 个数 ，里面包含的信息就有 P_1-P_2 的概率包含 p 的一个倍数！

此时之前那对 (x_i,x_j) 满足 \gcd(|x_i-x_j|,n) 一定为 n 的一个因数，且为 p 的一个倍数。

所以 \gcd(|x_i-x_j|,n) 一定是 n 的一个非平凡因子。

由此，我们将问题转化为下面这个形式 ：

暴力枚举进行判断是 O((n^{\frac{1}{4}})^2)=O(\sqrt n) 的，跟试除一个复杂度。

这个东西似乎也不好数据结构优化，这就是不能直接用 mt19937 随一个数列的原因。

Pollard 的伪随机数列

直接维护不好做，我们考虑在随机的数列上做文章。

我们需要使随机的数列有一些性质 ，使得只需要通过枚举少数几个 S 中的数即可判断是否存在 b 使得 \gcd(|a-b|,n)\ne 1

Pollard 给出了这样一个数列 :

我们考虑这个数列有什么好处呢？

而因为 |x_{i+1}-x_{j+1}|\in [0,n-1] , 所以 |x_{i+1}-x_{j+1}|=(|(x_i-x_j)\times (x_i+x_j)|\mod n)

发现仍满足 q|(|x_{i+1}-x_{j+1}|) 但有概率 x_i+x_j=n 而使其变为 0 或者其他情况使得 n|(|(x_i-x_j)\times(x_i+x_j)|) ，这样得到的 \gcd 不再是非平凡因子了，造成非平凡因子的损失。这样情况概率大约 \dfrac{1}{n} 量级，影响并不大，我们一会再讨论。

我们先讨论比较好的情况 ，即所有 (i,j) , 若 \gcd(|x_i-x_j|,n)\ne 1 则 \gcd(|x_{i+t}-x_{j+t}|,n)\ne 1 。

对于相同距离的点对 ，我们只需要每个距离只判断一次即可。

这样我们就可以有很多办法处理了，比如先加入 k 个，记为 x_1 到 x_k , 然后考虑第 k+1 个位置，我们对所有 i\in[1,k] 查是否有 \gcd(|x_i-x_{k+1}|,n)\ne 1 。

但由于要考虑到之前说的非平凡因子损失的情况，各种判法有实际表现上的差异。一个常用的是倍增判法：

判断每个 x_i 和 i 以下最大的 2 的整数次幂 j 是否 \gcd(|x_i-x_{j}|,n)\ne 1 。