目前来说，一般产生大素数的方法有两种：一种是概率素数测试法，另一种是确定性素数测试法。现已有许多种概率素数测试法，如Solovay-Strassen测试法、Lehman测试法及Miller_Rabin测试法等。这些算法基本上是以费尔马定理（Fermat Theorem）为基础，即：若N为素数，则对任意的整数a，0<a<N，必定满足a^(N-1) mod N =1 ，或a^((N-1)/2) mod N =±1 。
若N不满足上述条件，则N必为合数。但满足上述条件的N是否一定为素数？事实上并不尽然，还是有少许合数满足这些条件，这些合数称为假素数。但进一步判断，就可以以很高的概率得到素数。
一、Miller_Rabin测试法描述
设N>2且N是奇数，令N-1=(2^s)t，其中s≥1，且t为奇数。如果N是素数，则一定有a^(N-1) mod N =1 。
则下面的s+1个等式中必定满足一个：
a^t (mod N) =1
a^((2^i)t) (mod N)=-1 , i=0,1,2...,s-1
也就是说，如果N是素数，对任意选择的a∈{2,3,..,N-2}，必定会使上面s+1个等式中的一个成立。而如果对选择的a∈{2,3,..,N-2}，上面的s+1个等式均不成立，则一定可以判定N不是素数。根据此结果，Rabin引入了如下的素数集：
PN={a∈ZN:a^t mod N ≠1且?i<s ,a^((2^i)t) (mod N)≠-1}
Rabin算法：
1. 任取一个大奇数N。
2. 任取一正整数a∈{2,3,..,N-2}。
3. 如果gcd(a,N)=1且a?PN，则称N通过一次测试，即N有可能是素数；否则，N必定为合数。
4. 重复上述步骤2、3，任意选择不同的a共k次，以进行测试。
在实际运用中，可首先用300-500个小素数对N进行测试，以提高测试通过的概率和算法的速度。
二、代码实现如下
#include <iostream>
#include<string>
#include<cctype>
#include<assert.h>
#include<algorithm>
#include<ctime>
#include<cmath>using namespace std;
long long mod_fast(long long a,long long b,long long p)
{long long aa=a,t=1;while(b!=0){if(b&1)//是b和1做二进制的且运算 即看b的最后边那一位是不是1,是1的话 返回1 否则返回0{t=(t%p)*(aa%p)%p;}aa=(aa%p)*(aa%p)%p;b=b/2;//aa平方模}return t%p;
}
//Miller_Rabin算法
bool Miller_Rabin(long long n)
{long long a,s=0,num;long long t=n-1,mm=n-1;while(!(t & 1))//判断t是否为奇数，否则右移一位，相当于除2{t=t >> 1 ; //右移一位s++;//2的s次方}srand((unsigned)time(0));//设置随机数种子a=rand();//获取随机数anum=mod_fast(a,t,n);//判断第一个式子a^t mod n=1if(num==1){return true;}//进行s次判断for(int i=0;i<s;i++){if(num==mm)return true;else num=mod_fast(num,2,n);}return false;
}int main()
{long long n;bool flag=true;srand((unsigned)time(0));//设置随机数种子n=rand();//获取随机数n//保证n为素数if(!(n&1)){n=n+1;}while(flag){//利用Miller_Robin算法检测if(Miller_Rabin(n)){flag=false;cout<<n<<"通过Miller_Robin算法检测！"<<endl;}else{n=n+2;//不通过n加2继续检测}}return 0;
}三、运行结果
