Miller-Rabbin随机性素数测试算法

 1 //****************************************************************
 2 // Miller_Rabin 算法进行素数测试
 3 //速度快，而且可以判断 <2^63的数
 4 //****************************************************************
 5 const int S=20;//随机算法判定次数，S越大，判错概率越小
 6 
 7 
 8 LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63
 9 {
10     a%=mod;
11     b%=mod;
12     LL ans=0;
13     while(b)
14     {
15         if(b&1)
16         {
17             ans=ans+a;
18             if(ans>=mod)
19             ans=ans-mod;
20         }
21         a=a<<1;
22         if(a>=mod) a=a-mod;
23         b=b>>1;
24     }
25     return ans;
26 }
27 
28 LL pow_mod(LL a,LL b,LL mod) // a^b%mod
29 {
30     LL ans=1;
31     a=a%mod;
32     while(b)
33     {
34         if(b&1)
35         {
36             ans=mult_mod(ans,a,mod);
37         }
38         a=mult_mod(a,a,mod);
39         b=b>>1;
40     }
41     return ans;
42 }
43 
44 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
45 //一定是合数返回true,不一定返回false
46 
47 bool check(LL a,LL n,LL x,LL t)
48 {
49     LL ret=pow_mod(a,x,n);
50     LL last=ret;
51     for(int i=1;i<=t;i++)
52     {
53         ret=mult_mod(ret,ret,n);
54         if(ret==1 && last!=1 && last!=n-1) return true;//合数
55         last=ret;
56     }
57     if(ret!=1) return true;
58     else return false;
59 }
60 
61 // Miller_Rabin()算法素数判定
62 //是素数返回true.(可能是伪素数，但概率极小)
63 //合数返回false;
64 
65 bool Miller_Rabin(long long n)
66 {
67     if(n<2)return false;
68     if(n==2) return true;
69     if( (n&1)==0) return false;//偶数
70     LL x=n-1;
71     LL t=0;
72     while( (x&1)==0 ) { x>>=1;t++;}
73     for(int i=0;i<S;i++)
74     {
75         LL a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
76         if(check(a,n,x,t))
77         return false;//合数
78     }
79     return true;
80 }