提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
如何生成一个随机的大素数?
① 随机选取一个大奇数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两个解。
即:
if 1≤a≤n-1都有 an ≡a (mod n) ,也就是 an-1 mod n = 1, 因此 n 是一个素数
#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; }
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、返回素数。
#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 算法底层运算的优化,可以取得较以往实现更好的性能,这也是费马素性测试再无用武之地的原因。