Miller_Rabin 素数测试

费马定理的逆定理几乎可以用来判断一个数是否为素数，但是有一些数是判断不出来的，因此，Miller_Rabin测试方法对费马的测试过程做了改进，克服其存在的问题。

推理过程如下（摘自维基百科）：

摘自另一篇博文（手动滑稽）：

原理明白了，就直接上代码了（KuangBin大神的板子）：

代码思路是，

Miller_Rabin()函数随机选取 s 个a，a用做“基底”
check() 函数是用来判断x是否等于1,也就是判断a是否是n的凭证。
Mul_mod()函数是快速乘，求 a^t % n 之后的值是否为正负一，因为两个数直接乘的话会很大，可能会爆Long Long, 因此用快速乘边乘边mod。
pow_mod()函数是快速幂，在刚开始第一次判断 a^(n-1) % n 时会用到。

 /* *************************************************

 * Miller_Rabin 算法进行素数测试

 * 速度快可以判断一个 < 2^63 的数是不是素数

 *

 **************************************************/

 const int S = ; //随机算法判定次数一般 8 ∼ 10 就够了

 // 计算 ret = (a*b)%c

 //a,b,c < 2^63

 long long mult_mod(long long a,long long b,long long c)

 {

     a %= c;

     b %= c;

     long long ret = ;

     long long tmp = a;

     while(b)

     {

         if(b & )

         {

             ret += tmp;

             if(ret > c)ret -= c;//直接取模慢很多

         }

         tmp <<= ;

         if(tmp > c)tmp -= c;

         b >>= ;

     }

     return ret;

 }

 // 计算 ret = (a^n)%mod

 long long pow_mod(long long a,long long n,long long mod)

 {

     long long ret = ;

     long long temp = a%mod;

     while(n)

     {

         if(n & )ret = mult_mod(ret,temp,mod);

         temp = mult_mod(temp,temp,mod);

         n >>= ;

     }

     return ret;

 }

 // 通过 a^(n − 1)=1(mod n)来判断 n 是不是素数

 // n − 1 = x ∗ 2 t 中间使用二次判断

 // 是合数返回 true, 不一定是合数返回 false

 bool check(long long a,long long n,long long x,long long t)

 {

     long long ret = pow_mod(a,x,n);

     long long last = ret;

     for(int i = ; i <= t; i++)

     {

         ret = mult_mod(ret,ret,n);

         if(ret ==  && last !=  && last != n - )return true;//合数

         last = ret;

     }

     if(ret != )return true;

     else return false;

 }

 //**************************************************

 // Miller_Rabin 算法

 // 是素数返回 true,(可能是伪素数)

 // 不是素数返回 false

 //**************************************************

 bool Miller_Rabin(long long n)

 {

     if( n < )return false;

     if( n == )return true;

     if( (n&) == )return false;//偶数

     long long x = n - ;

     long long t = ;

     while( (x&)== )

     {

         x >>= ;

         t++;

     }

     srand(time(NULL));/* *************** */

     for(int i = ; i < S; i++)

     {

         long long a = rand()%(n - ) + ;

         if( check(a,n,x,t) )

             return false;

     }

     return true;

 }

巴特西

Miller_Rabin 素数测试

最新文章

热门文章