笔记 · 素性判断等（Miller-Rabin，Pollard-Rho）

aleph_ · 2025-08-24 12:16:26 · 个人记录

Miller-Rabin

两个引理

引理 1：费马小定理

设 p\in\text{Prime}，a\in\mathbb{Z}，且 \gcd(a,p)=1，那么有

证明：

对于两个整数 a\ne b\pmod p，和一个和 p 互素的整数 c，则有 ac\ne bc\pmod p.

考虑两组数：1,2,\dots,p-1；a,2a,\dots,(p-1)a。根据上述结论，两者均为模 p 的完全剩余系。

因此：

引理 2：二次探测定理

如果 p\in\text{Prime}，且 0<x<p，则方程 x^2\equiv 1\pmod p 的解为 x=1,p-1.

证明：

易知 x^2-1\equiv 0\pmod p

算法流程

费马小定理的缺陷是，有一些特殊的整数，虽然 a^{n-1}\equiv 1\pmod n，但 n 是合数。我们可以考虑通过随机化的方式，来规避这种数，这也是 Miller-Rabin 算法的核心思想。

• 对于 0,1,2 和偶数，可以直接判断。
• 设要测试的数是 N。我们取一个较小的质数 a。设 N-1=2^s\cdot t（其中 t 是奇数）。这有什么用呢？后面会说到。
• 对于 x=a^t，我们不断去平方他，进行二次探测检验。根据二次探测定理，如果 x^2\equiv 1\pmod N，但 x\ne 1 且 x\ne N-1，那么 N 就一定不是质数，退出。
• 我们最多可以平方 s 次，显然这期间 x 满足 0<x<N。最后 x=a^{2^s\cdot t}=a^{N-1}，再使用费马小定理进行验证。如果 a^{N-1}\not\equiv 1\pmod N，那么 N 肯定不是质数，退出。
• 注意，即使通过了上述检验，N 也可能不是质数。那么我们就多取几个质数 a，确保了检验的准确性。

注意事项

• 注意求平方的过程中，可能会爆 long long，需要用到龟速乘。怕超时的话，直接开 __int128
• 对于单个数 n，复杂度为 \mathcal{O}(k\log^3 n)，其中 k 为检验次数，此处 k=10。可以保证结果大概率正确。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int prime[10]={2,3,5,7,11,13,17,19,23,29};
int qmul(int a,int b,int mod){
    int ans=0;
    while(b){
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}
int qpow(int a,int b,int mod){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
bool Miller_Rabin(int n){
    if(n==2) return 1;
    if(n<2||!(n&1)) return 0;
    //特判0,1,2和偶数
    int s=0,t=n-1;
    while(!(t&1)){
        s++;
        t>>=1;
    }
    for(int i=0;i<10&&prime[i]<n;i++){
        int a=prime[i];
        int x=qpow(a,t,n);
        for(int j=1;j<=s;j++){
            int y=qmul(x,x,n);
            if(y==1&&x!=1&&x!=n-1) return 0;//二次探测检验
            x=y;
        }
        if(x!=1) return 0;//此时x=a^{n-1}，用费马小定理
    }
    return 1;
}
signed main(){
    int n;
    cin>>n;
    cout<<(Miller_Rabin(n)?"YES\n":"NO\n");
}

Pollard-Rho

算法概述

该算法能快速找到大整数的一个非1、非自身的因子。

原理这篇文章都讲透了

首先，可以考虑生成 [1,n] 的随机数 x，计算 d=\gcd(x,n)，若 d>1，那么就找到了，d 就是一个 n 的一个因子。

最坏情况下，n=p^2，p 是一个素数。那么当 x=p,2p,3p,\cdots,(p-1)p 时有 d>1，一共有 p-1\approx \sqrt{n} 个这样的 x，所以最差期望时间复杂度是 \mathcal{O}(\sqrt{n}\log n) 的。（log是算gcd带来的）

生日悖论

对于一个 [1,N] 内整数的理想随机数生成器，生成序列中第一个重复的数字前期望有 \sqrt{\frac{\pi N}{2}} 个数。(生日悖论)

对于 n=p^2，在 [1,n-1] 间生成的随机数模 p，大致是 [0,p-1] 间的随机数。因此期望在生成大约 \sqrt{p}=n^{\frac{1}{4}} 个数后，可以出现两个在模 p 意义下相同的数。那么这两个数的差 d，就满足 d\equiv 0\pmod p，也就满足 \gcd(d,n)>1，这时就找到了。但问题在于，我们没法两两进行比较验证，否则时间复杂度就会退回，还是没有进步。

伪随机数生成器

接下来是 Pollard-Rho 算法的精髓——使用一种特别的伪随机数生成器来生成 [0,n-1] 内的伪随机数序列。

设序列第一个数是 x，f(x)=(x^2+c)\mod n

则 x,f(x),f(f(x)),\dots 是生成的伪随机数序列。

观察这个伪随机数生成器，刚开始的时候是随机的，到后面就会进入一个环。因为下一个数是依赖于上一个数的，而可生成的数又是有限的，因此会有环。所以这个伪随机数生成器生成的数，可以看作是一条链，最终连向一个环。看起来就像字母 \rho。

我们可以使用龟兔赛跑算法（Floyd判环法）。

• 设置两个变量 t,r。每次判断是否有 |t-r|\equiv 0\pmod n，即判断 \gcd(|t-r|,n)>1。有的话，我们就找到了。这个期望显然是 n^{\frac{1}{4}}。
• 如果没有，那么令 t=f(t),r=f(f(r))，r 跑的快，所以如果最后没有找到答案，最终会在环上追上 t。这时退出，换一个 c 重新生成伪随机数。

注意到这个伪随机数生成器有一个性质。

对于 |i-j|\equiv 0\pmod p，有