Miller-Rabin 与 Pollard-Rho

这两个算法通常配合使用，用来处理较大的整数：

• Miller-Rabin：快速判断一个数是不是质数。
• Pollard-Rho：快速找到一个合数的非平凡因子。
• 找到因子后递归分解，就能求出一个大整数的全部质因数。

它们适合处理 $10^{18}$ 范围内的整数。

---

一、为什么普通质因数分解不够

判断 $n$ 是否为质数，最直接的方法是枚举

$2,3,\ldots,\lfloor\sqrt n\rfloor.$

如果 $n\le 10^{18}$，那么

$\sqrt n\le 10^9.$

一次判断可能需要接近 $10^9$ 次运算，无法接受。

Miller-Rabin 可以在大约 $O(\log n)$ 次模运算内完成一次检验。Pollard-Rho 则通常能在约 $O(n^{1/4})$ 的期望时间内找到一个因子。

---

二、Miller-Rabin 判素数

1. 从费马小定理开始

如果 $p$ 是质数，并且 $a$ 不是 $p$ 的倍数，那么

$a^{p-1}\equiv 1\pmod p.$

因此，若存在一个 $a$ 满足

$a^{n-1}\not\equiv 1\pmod n,$

那么 $n$ 一定不是质数。

但反过来不成立。有些合数对于很多 $a$ 也满足费马小定理，所以仅使用费马检验并不可靠。

Miller-Rabin 会进一步检查平方过程中出现的数，从而识别出更多合数。

---

2. 拆分 $n-1$

对于奇数 $n$，将 $n-1$ 写成

$n-1=d\cdot 2^s,$

其中 $d$ 是奇数。

例如

$561-1=560=35\cdot 2^4.$

所以

$d=35,\qquad s=4.$

---

3. 检验过程

选择一个底数 $a$，先计算

$x=a^d\bmod n.$

如果

$x=1$

或者

$x=n-1,$

那么这一轮暂时认为 $n$ 可能是质数。

否则不断平方：

$x\leftarrow x^2\bmod n.$

最多平方 $s-1$ 次。

如果某次得到

$x=n-1,$

这一轮检验通过。

如果始终没有得到 $n-1$，那么 $n$ 一定是合数。

---

4. 为什么要检查 $n-1$

对于质数 $p$，方程

$x^2\equiv 1\pmod p$

只有两个解：

$x\equiv 1\pmod p$

或

$x\equiv -1\pmod p.$

而模 $p$ 意义下的 $-1$ 就是 $p-1$。

假设不断平方后最终得到

$a^{p-1}\equiv 1\pmod p.$

那么在平方链中，第一次变为 $1$ 之前的数必须是 $-1$，否则就出现了一个既不是 $1$ 也不是 $-1$ 的平方根，与质数的性质矛盾。

Miller-Rabin 正是在检查这个过程。

---

5. $64$ 位整数的固定底数

对于无符号 $64$ 位整数，只需要检查下面这些底数，就可以得到确定性结果：

$ 2,\ 325,\ 9375,\ 28178,\ 450775,\ 9780504,\ 1795265022. $

也就是说，在 $64$ 位整数范围内，这套写法不是概率判素，而是可以当作确定性算法使用。

---

三、Pollard-Rho 找因子

Miller-Rabin 只能告诉我们一个数是不是质数。

如果 $n$ 是合数，还需要找到它的某个因子。Pollard-Rho 就负责完成这件事。

---

1. 构造伪随机序列

选择一个函数

$f(x)=x^2+c\pmod n.$

然后生成序列

$ x\_1=f(x\_0),\quad x\_2=f(x\_1),\quad x\_3=f(x\_2),\ldots $

由于所有数都在 $0$ 到 $n-1$ 之间，序列最终一定会出现重复，形状类似希腊字母 $\rho$，这也是 Pollard-Rho 名字的来源。

---

2. 为什么能找到因子

假设 $p$ 是 $n$ 的一个质因子。

虽然我们是在模 $n$ 的意义下生成序列，但也可以观察序列模 $p$ 后的结果。

因为 $p$ 通常比 $n$ 小，所以序列模 $p$ 后往往会更早发生碰撞。也就是存在两个位置 $i,j$，满足

$x\_i\equiv x\_j\pmod p.$

于是

$p\mid x\_i-x\_j.$

所以

$\gcd(|x\_i-x\_j|,n)$

可能得到 $p$，或者得到一个包含 $p$ 的非平凡因子。

---

3. Floyd 判环

不能保存整个序列，否则空间开销较大。

Pollard-Rho 使用快慢指针：

$x\leftarrow f(x),$

$y\leftarrow f(f(y)).$

然后计算

$d=\gcd(|x-y|,n).$

可能出现三种情况：

$d=1$

暂时没有发现因子，继续移动。

$1\<d\<n$

找到了一个非平凡因子，可以返回。

$d=n$

这次随机选择失败，需要重新选择初始值或常数 $c$。

---

四、完整分解过程

要分解整数 $n$，可以递归处理：

1. 如果 $n=1$，结束。
2. 使用 Miller-Rabin 判断 $n$。
3. 如果 $n$ 是质数，将其加入答案。
4. 否则使用 Pollard-Rho 找到因子 $d$。
5. 递归分解 $d$ 和 $n/d$。

例如分解

8051\.

Miller-Rabin 判断 $8051$ 是合数。

Pollard-Rho 可能找到因子

$d=83.$

于是

$8051=83\times 97.$

再分别判断 $83$ 和 $97$，二者都是质数，因此最终分解为

$8051=83\times 97.$

---

五、C++14 模板

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

ll mul(ll a, ll b, ll m) {
    return (i128)a * b % m;
}

ll qp(ll a, ll b, ll m) {
    ll r = 1;
    while (b) {
        if (b & 1) r = mul(r, a, m);
        a = mul(a, a, m);
        b >>= 1;
    }
    return r;
}

bool mr(ll n) {
    if (n < 2) return 0;

    for (ll p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n % p == 0) return n == p;
    }

    ll d = n - 1;
    int s = 0;

    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    for (ll a : {2LL, 325LL, 9375LL, 28178LL,
                 450775LL, 9780504LL, 1795265022LL}) {
        if (a % n == 0) continue;

        ll x = qp(a % n, d, n);
        if (x == 1 || x == n - 1) continue;

        bool ok = 0;

        for (int i = 1; i < s; i++) {
            x = mul(x, x, n);

            if (x == n - 1) {
                ok = 1;
                break;
            }
        }

        if (!ok) return 0;
    }

    return 1;
}

ll rho(ll n) {
    if (n % 2 == 0) return 2;
    if (n % 3 == 0) return 3;

    while (1) {
        ll c = rd() % (n - 1) + 1;
        ll x = rd() % (n - 2) + 2;
        ll y = x;
        ll d = 1;

        auto f = [&](ll v) {
            return (mul(v, v, n) + c) % n;
        };

        while (d == 1) {
            x = f(x);
            y = f(f(y));

            ll z = x > y ? x - y : y - x;
            d = gcd(z, n);
        }

        if (d != n) return d;
    }
}

void dfs(ll n, vector<ll> &a) {
    if (n == 1) return;

    if (mr(n)) {
        a.push_back(n);
        return;
    }

    ll d = rho(n);
    dfs(d, a);
    dfs(n / d, a);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    cin >> n;

    vector<ll> a;
    dfs(n, a);
    sort(a.begin(), a.end());

    for (ll x : a) cout << x << ' ';
    cout << '\n';

    return 0;
}

---

六、代码各部分作用

mul(a,b,m) 使用 __int128 计算

$a\times b\bmod m.$

因为 $a,b$ 可能接近 $10^{18}$，直接使用 long long 相乘会溢出。

qp(a,b,m) 计算

$a^b\bmod m.$

mr(n) 使用 Miller-Rabin 判断 $n$ 是否为质数。

rho(n) 返回 $n$ 的某个非平凡因子，但不保证返回质因子。

dfs(n,a) 递归分解。如果当前数是质数就直接加入答案，否则拆成两个部分继续分解。

---

七、常见错误

1. 直接使用 a * b % mod

当 $a,b$ 接近 $10^{18}$ 时，乘积可能达到 $10^{36}$，会在取模之前溢出。

需要使用 __int128。

2. Pollard-Rho 返回的一定是质数

Pollard-Rho 只保证返回一个非平凡因子，这个因子仍可能是合数，所以必须递归分解。

3. 得到 $d=n$ 后继续运行

当

$\gcd(|x-y|,n)=n$

时，说明这次随机序列没有成功分离出因子。需要重新随机选择 $c$ 和初始值。

4. 忘记处理偶数

Pollard-Rho 对偶数没有必要运行，直接返回因子 $2$ 更稳定。

5. 只使用少量普通底数判断所有 $64$ 位整数

例如只使用 $2,3,5,7$ 并不能保证覆盖整个 $64$ 位范围。应使用经过证明的固定底数集合。