Miller_Rabin--大素数判定算法

一篇很好的Miller_Rabin讲解博客 费马小定理:对于一个素数pp,对于任意整数aa,若gcd(a,b)=1\gcd(a,b)=1,则ap11(modp)a^{p-1}\equiv1(mod p) 如果要判断p是不是素数,就每次在[2,p1][2,p-1]中随机x,如果 则p不是素数。 但这还不够精确。 二次探测定理,对于一个奇素数pp,如果a21(modp)a^2\equiv1(mod p),则a1(modp)a\equiv1(mod p)ap1(modp)a \equiv p-1 (mod p) 我们可以把p1p-1分解成2tu2^t*u,然后令x[0]=aumodpx[0]=a^u mod px[i]=x[i1]2modpx[i]=x[i-1]^2 mod p,则x[t]=ap1x[t]=a^{p-1}如果x[i]=1x[i]=1,则x[i1]x[i-1]一定等于11p1p-1,否则p不为素数。如果x[t]1x[t]\neq 1pp同样不为素数。

当然2要特判。 每次判断错误率为14\frac{1}{4},判断ss次后错误率为(14)s(\frac{1}{4})^{s}。 时间复杂度O(slog3n)O(slog_3n) 如果p大,则乘法要用"类快速幂"计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
long long x;
long long f[128];
long long bigrand(long long l,long long r){
return (((long long)rand()<<31)+rand())%(r-l+1)+l;
}
long long mul(long long a,long long b,long long p){
long long c=0;
while(b){
if(b&1)c=(c+a)%p;
a=(a+a)%p;
b>>=1;
}
return c;
}
long long fpm(long long a,long long b,long long p){
long long c=1;
while(b){
if(b&1)c=mul(c,a,p);
a=mul(a,a,p);
b>>=1;
}
return c;
}
long long Miller_Rabin(long long x){
long long y=x-1,t=0;
if(x==2)return 1;
while(!(y&1)){y>>=1;++t;}
up(i,1,128){
long long k=bigrand(2,x-1);
f[0]=fpm(k,y,x);

up(j,1,t){
f[j]=mul(f[j-1],f[j-1],x);
if(f[j]==1&&f[j-1]!=1&&f[j-1]!=x-1){
return 0;
}
}
if(f[t]!=1)return 0;
}
return 1;
}
int main(){
long long n;
srand(2333);
n=read();
while(n){
--n;
x=read();
if(Miller_Rabin(x)){
printf("Yes\n");
}
else printf("No\n");

}
return 0;
}

文章目录
|

博客使用Disqus作为评论系统