蒙特卡罗算法之素数测试
1.、素数测试问题
数学原理
Wilson定理:对于给定的正整数n,判定n是一个素数的充要条件是(n-1)! -1(mod n)。
费尔马小定理:如果p是一个素数,且0<a<p,则a^(p-1)1(mod p)。 例如67是一个素数,则2^66mod67=1.利用费尔马小定理,对于给定的正整数n,可以设计一个素数判定算法。通过计算d=2^(n-1)mod n来判定整数n的素性。当d!=1时,n肯定不是素数;当d=1时,n则可能是素数。但也存在合数n使得2^(n-1)
1(mod n)。例如,满足此条件的最小合数是n=341。
二次探测定理:如果p是一个素数,且0<x<p,则方程x^21(mod p)的解为x=1,p-1。
Carmichael数:费尔马小定理是素数判定的一个必要条件。满足费尔马小定理条件的整数n未必全是素数。有些合数也满足费尔马小定理的条件,这些合数称为Carmichael数。前3个Carmichael数是561,1105,1729。Carmichael数是非常少的,在1~100000000的整数中,只有255个Carmichael数。
求a^m(mod n)的算法
设m的二进制表示为bkbk-1…b1b0(bk=1)。
例:m=41=101001(2),bkbk-1…b1b0=101001,(k=5)。
可以这样来求a^m:初始C←1。
b5=1:C←C^2(=1),∵bk=1,做C←a*C(=a);
b5b4=10:C←C^2(=a^2),∵bk-1=0,不做动作;
b5b4b3=101:C←C^2(=a^4),∵bk-2=1,做C←a*C(=a^5);
b5b4b3b2=1010:C←C^2(=a^10),∵bk-3= b2=0,不做动作;
b5b4b3b2b1=10100:C←C^2(=a^20),∵bk-4= b1=0,不做动作;
b5b4b3b2b1b0=101001:C←C^2(=a^40),∵bk-5= b0=1,做C←a*C(=a^41)。
最终要对am求模,而求模可以引入到计算中的每一步:
即在求得C2及a*C之后紧接着就对这两个值求模,然后再存入C。
这样做的好处是存储在C中的最大值不超过n-1,
于是计算的最大值不超过max{(n-1)^2,a(n-1)}。
因此,即便am很大,求am(mod n)时也不会占用很多空间。
代码实现:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
//随机化算法 蒙特卡罗算法 素数测试问题 //#include "stdafx.h" #include "RandomNumber.h" #include <cmath> #include <iostream> using namespace std; //计算a^p mod n,并实施对n的二次探测 void power(unsigned int a,unsigned int p,unsigned int n,unsigned int &result,bool &composite) { unsigned int x; if(p == 0) { result = 1; } else { power(a,p/2,n,x,composite); //递归计算 result = (x*x)%n; //二次探测 if((result == 1) && (x!=1) && (x!=n-1)) { composite = true; } if((p%2)==1) { result = (result*a)%n; } } } //重复调用k次Prime算法的蒙特卡罗算法 bool PrimeMC(unsigned int n,unsigned int k) { RandomNumber rnd; unsigned int a,result; bool composite = false; for(int i=1; i<=k; i++) { a = rnd.Random(n-3)+2; power(a,n-1,n,result,composite); if(composite || (result!=1)) { return false; } } return true; } int main() { int k = 10; for(int i=1010;i<1025;i++) { cout<<i<<"的素数测试结果为:"<<PrimeMC(i,k)<<endl; } return 0; }
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include"time.h" //随机数类 const unsigned long maxshort = 65536L; const unsigned long multiplier = 1194211693L; const unsigned long adder = 12345L; class RandomNumber { private: //当前种子 unsigned long randSeed; public: RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子 unsigned short Random(unsigned long n);//产生0:n-1之间的随机整数 double fRandom(void);//产生[0,1)之间的随机实数 }; RandomNumber::RandomNumber(unsigned long s)//产生种子 { if(s == 0) { randSeed = time(0);//用系统时间产生种子 } else { randSeed = s;//由用户提供种子 } } unsigned short RandomNumber::Random(unsigned long n)//产生0:n-1之间的随机整数 { randSeed = multiplier * randSeed + adder;//线性同余式 return (unsigned short)((randSeed>>16)%n); } double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数 { return Random(maxshort)/double(maxshort); }
实现结果:
参考文献:王晓东《算法设计与分析》第二版
https://blog.csdn.net/liufeng_king/article/details/9251589
相关文章
- R_Studio(cart算法决策树)对book3.csv数据用测试集进行测试并评估模型
- Java实现 蓝桥杯VIP 算法提高 士兵排队问题
- Java实现 蓝桥杯 算法提高 递推求值
- Java实现 蓝桥杯 算法提高 最大乘积
- 程序员的算法趣题Q08: 优秀的扫地机器人
- 排序算法大数据量测试结果
- 排序算法大数据量测试结果
- CV之NS之CycleGAN:基于apple2orange数据集利用TF框架的CycleGAN算法实现图像风格迁移/图像转换—训练&测试过程图文教程全记录
- DL之CNN:计算机视觉之卷积神经网络算法的简介(经典架构/论文)、CNN优化技术、调参学习实践、CNN经典结构及其演化、案例应用之详细攻略
- ML之K-means:基于DIY数据集利用K-means算法聚类(测试9种不同聚类中心的模型性能)
- TF:利用是Softmax回归+GD算法实现MNIST手写数字图片识别(10000张图片测试得到的准确率为92%)
- 基于麻雀算法优化的深度极限学习机DLM的预测算法(Matlab代码实现)
- leetcode算法第8题
- 【华为云技术分享】基于ModelArts AI市场算法MobileNet_v2实现花卉分类,支持CPU、GPU、Ascend推理
- m基于CNN卷积网络和GEI步态能量图的步态识别算法MATLAB仿真,测试样本采用现实拍摄的场景进行测试,带GUI界面
- 【算法】测试1 查找
- 【算法】测试2 排序
- isp 图像算法(二)之dead pixel correction坏点矫正
- 分治算法 汉诺塔 java
- 【youcans 的 OpenCV 例程200篇】123. 形态算法之孔洞填充
- 16. OD-破解序列号验证机算法
- 解决安装AI算法库TensorFlow 2.0的最新入坑指南以及详细的安装教程【分别在linux和windows系统下安装】