提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
一、伪大素数生成原理
如何生成一个随机的大素数？
方法一
① 随机选取一个大奇数n
②将从2开始的m个素数（2000以内）排列成数组，作为工具a[i]
③令i=0，计算x=n%a[i]
④ 判断，若x=0，说明n显然是合数，回到步骤1。若不等于0，说明暂且可以 认为n是素性的，进行步骤5。
⑤检测n%其他的a[i]． 当i=m-1，则将n视为一个伪素数，然后作为素数生成部分的结果。
方法二
对一个大奇数进行素性检测，如果不是素数，重新生成一个大奇数并再次检验，直至找到一个极大概率为素数的大奇数，即为伪大素数。本文采取此种方法生成伪大素数，素性判定算法分别选用费马小定理判别法和米勒拉宾素数判定法。
数学基础
Fermat 定理： n是一个奇素数，a是任何整数(1≤ a≤n-1) ，则 a^(n-1)≡1(mod n)。
Miller-Rabin算法是Fermat算法的一个变形改进，它的理论基础是由Fermat定理引申而来。
Miller-Rabin 算法的理论基础：
如果n是一个奇素数， 将n-1表示成2^s*r的形式(r是奇数)，a是和n互素的任何整数，那么a^r ≡1(mod n) 或者对某个j(0≤j ≤s －1， j∈Z) 等式 a^(2^j*r) ≡－1(mod n)成立。
这个理论是通过一个事实经由Fermat定理推导而来： n是一个奇素数，则方程x^2 ≡ 1 mod n只有±1两个解。
即：
二、费马小定理判别法
1.算法
if 1≤a≤n-1都有 an ≡a (mod n) ,也就是 an-1 mod n = 1, 因此 n 是一个素数
2.代码实现
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
/*使用三个rand()生成伪随机数组合生成一个奇数随机数，作为伪素数
**系统时间为种子
**并返回生成的这个大奇数
*/
unsigned int ProduceRandomOdd(){//UINT无符号整形，各伪随机数放在RandomArray数组中
time_t t;//c++时间类型
unsigned int RandomNumber;//记录随机数
do{
srand((unsigned)time(&t));//srand(seed)用于给rand()函数设定种子,此处用系统时间
//生成
RandomNumber=(rand()<<17)|(rand()<<3)|(rand());
//cout<<RandomNumber<<endl;
}while(RandomNumber%2==0||RandomNumber<100000000);
//返回
return RandomNumber;
}
long long qmod(int a, int b, int p) {
long long res = 1;
long long term = a%p;
while(b) {
if(b&1){
res = (res*term)%p;
}
term = (term*term)%p;
b >>= 1;
}
return res;
}
bool Fermat_prime(long long n) {
int i;
for(i = 0; i < 100; ++i) {
if(qmod(1+rand()%(n-1),n-1, n) != 1)
break;
}
if(i < 100)
return false;
else
return true;
}
int main(){
unsigned int RandomOdd;
bool flag;
//直至找到过关的伪素数
do{
RandomOdd=ProduceRandomOdd();
//cout<<RandomOdd<<endl;
flag=Fermat_prime(RandomOdd);
}while(flag==false);
//cout<<"=========================="<<endl;
cout<<"生成的一个伪素数为：" <<RandomOdd;
}
二、米勒拉宾素数判定法
1.算法
Miller-Rabin(n,t)
输入：一个大于3的奇整数n和一个大于等于1的安全参 数t(用于确定测试轮数)。
输出：返回n是否是素数(概率意义上的，一般误判概率小于(1/2)80即可) 。
1、将n-1表示成2sr，(其 中 r是奇数)
2、 对i从1到 t 循环作下面的操作：
2.1选择一个随机整数a(2≤a ≤n-2)
2.2计算y ←ar mod n
2.3如果y≠1并且y ≠n-1作下面的操作,否则转3：
2.3.1 j←1;
2.3.2 当j≤s-1 并且y≠n-1循环作下面操作,否则跳到 2.3.3：
{计算y ←y2 mod n;
如果 y=1返回 合数 ；
否则 j←j+1; }
2.3.3如果y ≠n-1 则返回 合数 ；
3、返回素数。
2.代码实现
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
//#include <cstddef.h>
using namespace std;
/*使用三个rand()生成伪随机数组合生成一个奇数随机数，作为伪素数
**系统时间为种子
**并返回生成的这个大奇数
*/
unsigned int ProduceRandomOdd(){//UINT无符号整形，各伪随机数放在RandomArray数组中
time_t t;//c++时间类型
unsigned int RandomNumber;//记录随机数
do{
srand((unsigned)time(&t));//srand(seed)用于给rand()函数设定种子,此处用系统时间
//生成
RandomNumber=(rand()<<17)|(rand()<<3)|(rand());
//cout<<RandomNumber<<endl;
}while(RandomNumber%2==0||RandomNumber<100000000);
//返回
return RandomNumber;
}
//模重复平方算法求(b^n)%m
size_t repeatMod(size_t base, size_t n, size_t mod){
size_t a = 1;
while(n){
if(n&1){
a=(a*base)%mod;
}
base=(base*base)%mod;
n=n>>1;
}
return a;
}
//Miller-Rabin素数检测
bool rabinmiller(size_t n, size_t k){
int s=0;
int temp=n-1;
//将n-1表示为(2^s)*t
while ((temp&0x1)==0&&temp){
temp=temp>>1;
s++;
}
size_t t = temp;
//判断k轮误判概率不大于(1/4)^k
while(k--){
srand((unsigned)time(0));
size_t b = rand()%(n-2)+2; //生成一个b(2≤a ≤n-2)
size_t y = repeatMod(b,t,n);
if (y == 1 || y == (n-1))
return true;
for(int j = 1; j<=(s-1) && y != (n-1); ++j){
y = repeatMod(y,2,n);
if (y == 1)
return false;
}
if (y != (n-1))
return false;
}
return true;
}
int main(){
size_t k=80;//进行80轮测试
unsigned int RandomOdd;
bool flag;
//直至找到过关的伪素数
do{
RandomOdd=ProduceRandomOdd();
//cout<<RandomOdd<<endl;
flag=rabinmiller(RandomOdd,k);
}while(flag==false);
//cout<<"=========================="<<endl;
cout<<"生成的一个伪素数为：" <<RandomOdd;
}
三、不同算法特点及优劣比较
①Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。
②通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时， Miller-Rabin算法是完成素数测试的最佳选择。
③通过对Miller-Rabin 算法底层运算的优化，可以取得较以往实现更好的性能，这也是费马素性测试再无用武之地的原因。