Miller-Rabin与Pollard-Rho——学习笔记

有关大数质因数分解的两个算法。

\(Miller-Rabin\) 判断一个数是否是质数,有很小的概率会错。

借助费马小定理,二次探测定理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool Miller_Rubbin(LL n){
if(!(n%2)) return n==2; if(!(n%3)) return n==3;
if(!(n%5)) return n==5; if(!(n%7)) return n==7;
if(!(n%11)) return n==11; if(!(n%13)) return n==13;
for(int T=8;T;T--){
LL y,t,s; for(y=n-1,t=0;!(y&1);y>>=1,t++);
LL x=Pow(rand()%(n-2)+2,y,n);
if(x==1) continue;
while(t--){
s=Mul(x,x,n);
if(s==1){ if(x!=n-1) return false; break; }
x=s;
}
if(s!=1) return false;
}
return true;
}

\(Pollard-Rho\)

很神奇的一种方法,可以期望 \(O(n^{\frac 1 4})\) 找到一个数的小约数,从而实现大数分解。

大概是借助 \(floyed\) 判环,随机出 \(x\)\(n\) 的约数的倍数, \(gcd(x,n)>1\)

中间要用 \(Miller-Rabin\) 判是否已经是质数了。

复杂度的伪证:设随机数列为 \(a_i\) , 设 \(d\)\(n\) 的一个约数 , 设 \(b_i = a_i \text{ % }d\)

\(a_i\) 期望 \(\sqrt n\) 步出现循环,\(b_i\) 期望 \(\sqrt d\) 步出现循环。所以基本上 \(b_i\) 先于 \(a_i\) 循环。

\(b_i=b_j\)\(d|(a_i-a_j)\) ,就找到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }
inline LL findD(LL n){
LL x=rand()%(n-1)+1,y=x,rdm=rand()%(n-1)+1;
for(int t=0,k=1;;){
x=(Mul(x,x,n)+rdm)%n;
if(x==y) return -1;
LL g=gcd(x>y?x-y:y-x,n); if(g>1) return g;
if((++t)==k) k<<=1,y=x;
}
}
map <LL,int> F;
inline void Pallard(LL n){
if(n==1) return;
if(Miller_Rubbin(n)) return ++F[n],printf("%d\n",n), void();
LL d; while((d=findD(n))==-1);
Pallard(d); Pallard(n/d);
}