C++实现伪大素数生成算法(费马小定理判别法、米勒拉宾素数判定法)
2021/10/14 20:14:40
本文主要是介绍C++实现伪大素数生成算法(费马小定理判别法、米勒拉宾素数判定法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 一、伪大素数生成原理
- 方法一
- 方法二
- 数学基础
- 二、费马小定理判别法
- 1.算法
- 2.代码实现
- 二、米勒拉宾素数判定法
- 1.算法
- 2.代码实现
- 三、不同算法特点及优劣比较
一、伪大素数生成原理
如何生成一个随机的大素数?
方法一
① 随机选取一个大奇数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 算法底层运算的优化,可以取得较以往实现更好的性能,这也是费马素性测试再无用武之地的原因。
这篇关于C++实现伪大素数生成算法(费马小定理判别法、米勒拉宾素数判定法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享