Pollard's rho 大整数分解

Pollard's rho 是一种用于大整数分解的随机化算法。它可以在 $O(n^{1/4})$ 的期望时间内找到 $n$ 的一个非平凡因子。在实际应用中，通常配合 Miller-Rabin 素性测试来实现高效的质因数分解。

Miller-Rabin 素性测试

在对大整数进行分解前，首先需要判断该数是否为素数。对于 $10^{18}$ 范围内的数，传统的 $O(\sqrt{n})$ 算法失效，通常采用 Miller-Rabin 随机化素性测试。

原理

Miller-Rabin 基于费马小定理的逆命题（尽管逆命题不完全成立）以及二次探测定理：

• 费马小定理：如果 $p$ 是素数，则对于任意 $1 \le a < p$，有 $a^{p-1} \equiv 1 \pmod p$。
• 二次探测定理：如果 $p$ 是素数，且 $x^2 \equiv 1 \pmod p$，则 $x \equiv 1 \pmod p$ 或 $x \equiv p-1 \pmod p$。

常用测试底数

对于 $2^{64}$ 范围内的整数，选取 $\{2, 3, 5, 7, 11, 13, 17, 19, 23\}$ 作为底数进行测试，即可保证结果的确定性。

Pollard's rho 算法

Pollard's rho 的核心思想是利用生日悖论。如果我们随机生成序列，出现重复项的速度比想象中要快。

伪随机序列

算法通过迭代函数 $f(x) = (x^2 + c) \bmod n$ 生成一个伪随机序列。由于 $n$ 是合数，设其有一个因子 $p$，那么在序列模 $p$ 的意义下，序列会在 $O(\sqrt{p})$ 步内进入循环。

只要我们找到两个项 $x_i, x_j$ 满足 $x_i \equiv x_j \pmod p$ 但 $x_i \not\equiv x_j \pmod n$，则 $\gcd(|x_i - x_j|, n)$ 就是 $n$ 的一个非平凡因子。

优化：倍增与 GCD 组合

频繁调用 $\gcd$ 函数开销较大。我们可以利用性质：若 $\gcd(a, n) > 1$，则 $\gcd(ab \bmod n, n) \ge \gcd(a, n) > 1$。 通过将一段差值累乘后再统一求一次 $\gcd$，可以显著提升运行效率。通常每 127 次迭代进行一次 $\gcd$ 校验。

实现 (C++)

以下实现支持 $2^{64}$ 范围内的整数处理，使用了 __int128 处理大数乘法。

#include <vector>
#include <algorithm>
#include <random>

using namespace std;

typedef long long ll;
typedef __int128_t int128;

struct PollardRho {
    mt19937_64 rng;

    PollardRho() : rng(random_device{}()) {}

    ll power(ll a, ll b, ll m) {
        ll res = 1;
        a %= m;
        while (b) {
            if (b & 1) res = (ll)((int128)res * a % m);
            a = (ll)((int128)a * a % m);
            b >>= 1;
        }
        return res;
    }

    bool miller_rabin(ll n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        ll d = n - 1;
        int s = 0;
        while (d % 2 == 0) d /= 2, s++;
        static const vector<ll> bases = {2, 3, 5, 7, 11, 13, 17, 19, 23};
        for (ll a : bases) {
            if (n <= a) break;
            ll x = power(a, d, n);
            if (x == 1 || x == n - 1) continue;
            bool composite = true;
            for (int r = 1; r < s; ++r) {
                x = (ll)((int128)x * x % n);
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite) return false;
        }
        return true;
    }

    ll gcd(ll a, ll b) {
        return b ? gcd(b, a % b) : a;
    }

    ll get_factor(ll n) {
        if (n % 2 == 0) return 2;
        if (miller_rabin(n)) return n;
        
        uniform_int_distribution<ll> dist(1, n - 1);
        while (true) {
            ll c = dist(rng);
            auto f = [&](ll x) { return (ll)(((int128)x * x + c) % n); };
            ll x = 0, y = 0, s = 1, g = 1;
            for (int goal = 1; ; goal <<= 1, y = x, s = 1) {
                for (int step = 1; step <= goal; ++step) {
                    x = f(x);
                    s = (ll)((int128)s * abs(x - y) % n);
                    if (step % 127 == 0) {
                        g = gcd(s, n);
                        if (g > 1) return g;
                    }
                }
                g = gcd(s, n);
                if (g > 1) return g;
            }
        }
    }

    void factorize(ll n, vector<ll>& factors) {
        if (n == 1) return;
        if (miller_rabin(n)) {
            factors.push_back(n);
            return;
        }
        ll d = get_factor(n);
        factorize(d, factors);
        factorize(n / d, factors);
    }

    vector<ll> get_prime_factors(ll n) {
        vector<ll> factors;
        factorize(n, factors);
        sort(factors.begin(), factors.end());
        return factors;
    }
};

总结

Pollard's rho 是一种极具技巧性的随机化算法。在实际应用中，处理好 __int128（或手动实现大数取模乘法）以及 $\gcd$ 优化是提高效率的关键。该算法在密码学（如 RSA 破解）和数论竞赛中具有重要地位。