首页 > 代码库 > Miller_Rabbin大素数测试

Miller_Rabbin大素数测试

2024-09-22 14:13:10   217人阅读

  伪素数： 如果存在和n互素的正整数a满足a^(n-1)≡1(mod n)，则n是基于a的伪素数。

　　是伪素数但不是素数的个数是非常非常少的，所以如果一个数是伪素数，那么他几乎是素数。

　Miller_Rabbin素数测试：随机选k个a进行a^(n-1)≡1(mod n)测试，如果都满足则判断n是素数。

　　a^(n-1)%mod用快速幂计算。对于大数相乘（两个大于int的数相乘），中间结果可能溢出，所以需要用快速幂思想进行乘法取模。

　Miller_Rabbin的出错率为2^(-k)。

 1 //Miller Rabbin [1,2^63)的内大素数测试
 2 
 3 //快速幂思想计算(a*b)%mo,防止中间结果溢出
 4 //当a*b结果在longlong内时请不要用这一函数，否则可能Tle
 5 LL mult(LL a,LL b,LL mo)
 6 {
 7     LL ret=0,x=a%mo,y=b%mo;
 8     while(y)
 9     {
10         if(y&1) ret=(ret+x)%mo;
11         x=(x<<1)%mo,y>>=1;
12     }
13     return ret;
14 }
15 //快速幂取模
16 LL qpow(LL x,LL y,LL mo)
17 {
18     LL ret=1;
19     while(y)
20     {
21         if(y&1) ret=mult(ret,x,mo);
22         x=mult(x,x,mo),y>>=1;
23     }
24     return ret;
25 }
26 //不断测试a^(x-1)%x=1
27 bool Miller_Rabbin(LL x)
28 {
29     if(x==2||x==3||x==5||x==7) return 1;
30     if(x<2||x%2==0||x%3==0||x%5==0||x%7==0) return 0;
31     for(int i=1;i<=30;i++)
32     if(qpow(rand()%(x-2)+2,x-1,x)!=1)
33         return 0;
34     return 1;
35 }

 

Miller_Rabbin大素数测试


联系
我们