[SinGuLaRiTy] 米勒罗宾素数判定法
2018-06-18 01:10:54来源:未知 阅读 ()
【SinGuLaRiTy-1003】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
背景
数论学家利用费马小定理研究出了多种素数测试办法,Miller-Rabbin 素数测试算法是其中较快的一种。
步骤
(1)计算奇数M,使得N=2^r * M + 1;
(2)选择随机数A<N;
(3)对于任意i<r,若A^(2^i*M) mod N = N - 1,则N通过随机数A的测试;
(4)或者,若A^M mod N = 1,则N通过随机数A的测试;
(5)让A取不同的值对N进行行多次测试(一般要求5~10次,有较高要求的话可以进行20~30次),若全部通过则判定N为素数;
概率
若N通过一次测试,则N不是素数的概率为25%;
若N通过 t 次测试,则N不是素数的概率为1/( 4 ^ t );
事实上,当 t = 5 时,N不是素数的概率已为1/128,已经大于99.99%。
在实际运用中,可首先用300~500个小素数对N进行测试,以提高测试通过的概率与算法的速度。在随机生成的素数中,选取的随机数最好让 r = 0,则可以省去步骤(3)的操作,进一步减少判定时间。
代码
#include<cstdlib> #include<ctime> #include<cstdio> using namespace std; const int count=10; int modular_exp(int a,int m,int n) { if(m==0) return 1; if(m==1) return (a%n); long long w=modular_exp(a,m/2,n); w=w*w%n; if(m&1) w=w*a%n; return w; } bool Miller_Rabin(int n) { if(n==2) return true; for(int i=0;i<count;i++) { int a=rand()%(n-2)+2; if(modular_exp(a,n,n)!=a) return false; } return true; } int main() { srand(time(NULL)); int n; scanf("%d",&n); if(Miller_Rabin(n)) printf("Probably a prime."); else printf("A composite."); printf("\n"); return 0; }
Time:2017-02-07
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:类和结构(一)
- POJ 1811 大素数判断 2018-06-17
- [SinGuLaRiTy] 高精度算法代码库 2018-06-17
- [SinGuLaRiTy] 最短路计算代码库 2018-06-17
- [SinGuLaRiTy] 组合数学 2018-06-17
- [SinGuLaRiTy] 平衡树 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash