Miller Rabin
PON - Prime or Not
若 $p$ 为素数，那么 $\forall p \nmid a, a^{p-1} \equiv 1 (\mod p)$。
若 $p$ 为奇素数，那么 $x^2 \equiv 1(\mod p)$ 的解为 $x \equiv \pm 1(\mod p)$。
取前 $12$ 个素数（$2,3,5,7,11,13,17,19,23,29,31,37$）就够用了。OEIS。
时间复杂度 $O(\log V)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| inline int qm(int x,int y,int p){ int res=1; for(;y;y>>=1,x=(i128)x*x%p) if(y&1) res=(i128)res*x%p; return res; }
int pr[15]={0,2,3,5,7,11,13,17,19,23,29,31,37};
int chk(int x,int p){
int d=p-1,cur; for(;!(d&1);d>>=1);
cur=qm(x,d,p); if(cur==1) return 1;
for(;d<=p-1;d<<=1){
if(cur==p-1) return 1;
cur=(i128)cur*cur%p;
}
return 0;
}
int chk(int p){
if(p>37){ for(int i=1;i<=12;++i) if(!chk(pr[i],p)) return 0; return 1; }
else{ for(int i=1;i<=12;++i) if(pr[i]==p) return 1; return 0; }
}
|
Pollard Rho
【模板】Pollard-Rho
构造函数 $f(x)=x^2+c$，记 $x_0=0,x_i=f(x_{i-1})$。
每次找 $\gcd(\Delta x,p)$ 是很优的。
$x_i$ 会形成类似 $\rho$ 的图形，由生日悖论可知其长度期望为 $O(\sqrt[4]{p})$，考虑枚举 $i$，当 $x_{2i}=x_i$ 时退出，这样来判环。
期望时间复杂度 $O(\sqrt[4]{n}\log n)$。
根据 $\gcd(a,n) \mid \gcd(ab \mod n,n)$，将 $\Delta x$ 乘起来，达到一定限度是求 $\gcd$ 判断。
对限度倍增，与 $128$ 取 $\min$ 较优。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #define get(l,r) (rnd()%((r)-(l)+1)+(l))
mt19937_64 rnd(time(0));
inline int qm(int x,int y,int p){ int res=1; for(;y;y>>=1,x=(i128)x*x%p) if(y&1) res=(i128)res*x%p; return res; }
int div(int p){
int c=get(1,p-1),s=c,t=0,prod=1,lim=1,cnt=0,d;
auto f=[&](int x){ return ((i128)x*x+c)%p; };
for(;s!=t;s=f(f(s)),t=f(t)){
prod=(i128)prod*abs(s-t)%p;
if(++cnt==lim){
if((d=__gcd(prod,p))!=1) return d;
cnt=0,lim=min(lim<<1,B);
}
}
if((d=__gcd(prod,p))!=1) return d; return p;
}
int find(int p){
if(p==1) return 1;
if(chk(p)) return p;
int d=div(p); for(;d==p;d=div(p));
for(;p%d==0;p/=d);
return max(find(d),find(p));
}
|
参考
Pollard Rho
初等数论学习笔记 II：分解质因数