Pollard-Rho 是用来分解大数质因子的一个玩意。
Miller-Rabin 素性判断
众所周知,费马告诉我们对于一个素数 p,有 ap−1≡1(modp)。
然鹅它的逆命题是不成立的,即 ap−1≡1(modp) 不是 p 的充分条件。
不过,大部分合数都可以被这个式子筛掉,所以我们可以基于这个式子进行下一步改进。
然后有二次探测定理:对于素数 p,如果有 a2≡1(modp),那么有 a≡1(modp) 或 a≡−1(modp)。
简单地证明一下:
x2=(x+1)(x−1)+1。
所以 (x+1)(x−1)≡0(modp)。
要么 x+1≡0(modp),要么 x−1≡0(modp)。
然后易得那两个式子。
考虑到费马小定理和二次探测定理的形式很像,并且 p−1 一定为偶数,所以我们可以一直运用二次探测定理。
对于不同的 a,我们把上述算法称之为 以 a 为底的 Miller-Rabin 测试。
一般底数仍然是随机选取,但当待测数不太大时,选择测试底数就有一些技巧了。
比如,如果被测数小于 4759123141,那么只需要测试三个底数 2,7,61 就足够了。
当然,你测试的越多,正确的范围肯定也越大。如果你每次都用前 7 个素数 (2,3,5,7,11,13,17) 进行测试,所有不超过 341550071728320 的数都是正确的。
如果选用 2,3,7,61,24251 作为底数,那么 1016 内唯一的强伪素数为 46856248255981。
这样的一些结论使得 Miller-Rabin 算法在OI中非常实用。
——Matrix67
根据本人测试,对于上面那个 46856248255981,增加底数 19∗∗∗∗17 即可。
(大雾)
代码
1 | //洛谷 3383.「模板」线性筛素数 |
Pollard-Rho
考虑对于一个合数 n,它的一个质因子为 p,如果有 a≡b(modp) 但 a≢b(modn),那么 |a−b| 便是 n 的一个非平凡因子。
所以一个比较暴力的方法就是一直随机两个数并计算它们的差与 n 的 gcd 然后递归做。
然鹅这样子考虑到随机数的效率和质量,并没有什么卵用……
我们考虑手写随机数,设我们生成的第 i 个随机数是 xi,并选取一个常数 c,有 xi≡x2i−1+c(modn)。
但是接下来又有一个问题,怎样提高准确率?
显然地,x 数列会出现循环。如果 xi≡xj(modd) (i<j),那么数列在模 d 意义下是周期的,其长度整除 j−i。
那么对于 j−i 最小的 >i 的倍数 s,有 xs≡x2s(modd)。
所以我们可以对于 xk 与 x2k 进行这个过程。
又有一个问题,如果判环?
哈希?太麻烦了!
考虑在一个环上,甲、乙从同一个点出发,甲经过一条边的时间乙能经过两条边,甲、乙向同一个方向走。
那么当乙追上甲时,甲一定至少走了一圈。
这个方式恰好可以与上面的过程结合起来。
在实际应用中,一定要注意先用线性筛出空间允许的范围内的素数并试除,最后再上 Pollard-Rho。
因为它只能找到部分较大的质因子。
代码
1 | //洛谷 4718.「模板」Pollard-Rho 算法 |