费马定理的逆定理几乎可以用来判断一个数是否为素数，但是有一些数是判断不出来的，因此，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;
}