Pollard Rho 算法

定义

Pollard Rho 算法是一种快速分解大整数的随机化算法。

求解算法

思路与简单证明

对整数 \(n\)，先用 Miller-Rabin 算法 判断是否为素数；若不是，则用 Pollard Rho 找到一个非平凡因子 \(d\)，再递归分解 \(d\) 和 \(\frac{n}{d}\)。

算法迭代伪随机函数 \(f(x) = (x^2 + c) \bmod n\)，并用 Floyd 判圈法维护慢指针 \(x\) 与快指针 \(y = f(f(y))\)。当 \(\gcd(|x-y|, n)\) 落在 \(1\) 与 \(n\) 之间时，即得到一个因子；若它等于 \(n\)，则重新选择初始值和 \(c\)。

实现

下列代码复用 Miller-Rabin 算法 中的 u64、mul_mod 与 is_prime。

#include <chrono>
#include <map>
#include <numeric>
#include <random>

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

u64 f(u64 x, u64 c, u64 mod) {
    return (mul_mod(x, x, mod) + c) % mod;
}

u64 pollard_rho(u64 n) {
    if (n % 2 == 0) return 2;
    while (true) {
        u64 c = rng() % (n - 1) + 1;
        u64 x = rng() % n, y = x, d = 1;
        while (d == 1) {
            x = f(x, c, n);
            y = f(f(y, c, n), c, n);
            u64 diff = x > y ? x - y : y - x;
            d = std::gcd(diff, n);
        }
        if (d != n) return d;
    }
}

void factor(u64 n, std::map<u64, int>& result) {
    if (n == 1) return;
    if (is_prime(n)) {
        ++result[n];
        return;
    }
    u64 d = pollard_rho(n);
    factor(d, result);
    factor(n / d, result);
}