#include <iostream>
#include <vector>
#include <math.h>
#include <time.h>
#include <algorithm>
using namespace std;
unsigned long long MOD_EXP(unsigned long long A,\
unsigned long long B,\
unsigned long long N){ // (A^B)%N
unsigned long long D = 1;
vector<int> R;
while((B!=0)){
R.push_back(B%2);
B=B/2;
}
for(int i=R.size()-1;i>=0;i--){
D = (D*D) % N;
if(R[i] == 1){
D = (D*A) % N;
}
}
return D;
}
inline unsigned long long RandInt(unsigned long long x,unsigned long long y)
{return rand()%(y-x+1)+x;}
bool MILLER_RABIN(unsigned long long N){
unsigned long long TEST_NUM[] = {2,7,61};
unsigned long long S = 0;
unsigned long long T = N-1;
while(T % 2 == 0){
S++;
T = T/2;
}
for(int i=0;i<3;i++){
if(TEST_NUM[i] < N){
vector<unsigned long long> X;
X.resize((int)S+1);
X[0] = MOD_EXP(TEST_NUM[i],T,N);
for(unsigned long long j=1;j<=S;j++){
X[j] = MOD_EXP(X[j-1],2,N);
if(X[j]==1 && X[j-1]!=1 && X[j-1]!=(N-1))
return false;
}
if(X[S] != 1)
return false;
}
}
return true;
}
int main()
{
unsigned long long index = 0;
for(unsigned long long i=2;i<1000000000;i++){
if(MILLER_RABIN(i) == true)
index++;
}
cout<<index<<endl;
return 0;
}
if n < 9,080,191, it is enough to test a = 31 and 73.
if n < 4,759,123,141, it is enough to test a = 2, 7, and 61.
if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13.
if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.
测试数据:
第100个素数:541
第1,000个素数:7919
第10,000个素数:104729
第100,000个素数:1299709
第1,000,000个素数:15485863
100内有:25个素数
1,000内有:168个素数
10,000内有:1229个素数
100,000内有:9592个素数
1,000,000 内有:78498个素数
10,000,000内有:664579个素数
100,000,000内有:5761455个素数
程序很简单 先把A^(N-1) 改成 A^(2^S*T) 的方式
从A^(2^1*T)%N 试到 A^(2^S*T)%N 哪个不等于1 就返回非质数 都通过就返回质数
苦于SPOJ第二题超时的同学 快拿这个测试 去秒杀它吧 哈哈哈哈
分享到:
相关推荐
程序实现了Miller-Rabin算法判断一个数是否是素数
公共密钥体系中,一般选择的素数都是相当大的(通常在100位以上),如果采用上次的试除法来判定,那么可能要穷尽你一生的时间都还不够。所以在一般的应用领域,人们采用的是Rabin-...本文描述Miller-Rabin素性测试算法
Miller-Rabin素数检测优化算法研究及其并行实现.pdf 含有证明
//对Miller-Rabin算法的进一步改进,速度约为0.4秒验证一个素数(CPU为赛扬1.5G) //本程序使用Miller Rabin方法计算1024位素数(2进制)
实现Miller-Rabin素数判定算法.zip
用c语言实现了Miller-Rabinchect算法,可以快速检验不是很大的整数是否为素数
求质数的算法之Miller-Rabin费马小定理
1.产生一个随机数在2的l次方跟2的l+1次方间,用Miller-rabin测试它是否是一个素数。 2.给出x和n,用扩展的欧几里得算法计算x的逆y(mod n)。 3.调用上面的两个函数,产生ras参数n=p*q,e和d。 4.给出信息M,用你...
MILLER-RABIN 素数测试算法课程报告 内含代码
Elgamal public key encryption algorithm;Elgamal 公钥加密算法 Miller-Rabin probabilistic primality testing algorithm 素数判定测试 RSA 和 CRT 公钥加解密 ECDH 和 DH 密钥交换
2、对该整数进行小素数检验,在进行miller_rabin算法检测 3、获得大素数p、q后,计算n、e、的d过程有说明 4、可以对任意数字字母汉字加解密 5、内容的注释详细,易理解;用像伪代码般的python码出来的更容易对代码...
通过将Miller-Rabin素性检测的思想拓展到多项式域,随机二分搜索可应用到多项式分解中。并以此为基础,分别针对有限域和代数数域改进了两种概率性算法。第一种算法在有限域上每次分解模素数的多项式的失败概率最多为...
南开大学机器人与信息自动化研究所,通过比较各种素数测试算法和对miller-rabin算法进行研究,证明在计算机中构建密码安全体系时,miller-rabin算法是完成素数测试的最佳选择。通过对miller-rabin算法底层运算的优化...
Miller-Rabin 素性检验此示例提供了在 Haskell 中Miller-Rabin 素性测试 [1]的实现。 请注意,这不是确定性测试。 该测试使用 20 个随机见证人检查素性。 可以在函数isprime更改此列表。 更长的证人名单将产生更准确...
Rabin-Miller快速素数测试,使用蒙格马利快速幂取模实现,时间复杂度O(t*log(n))
64位以内Rabin-Miller 强伪素数测试和Pollard rho 因数分解算法的实现的C代码
它的功能非常强大,接口很简单,其中不但有普通的整数、实数、浮点数的高精度运算,还有随机数生成,尤其是提供了非常完备的数论中的运算接口,比如Miller-Rabin素数测试算法,大素数生成,欧几里德算法,求域中元素...
随机产生的任意大小的数,并验证其是否为素数。
primality_test Miller检验-Miller–Rabin素数检验的未经证实的确定性版本
波拉德-rho-分解器使用 Pollard-Rho 算法将数字分解为质因数,并使用 Miller-Rabin 检验验证质数。 当前编程为在作为参数给出的范围内SSN * (10 ^ 6 + j) + i 。 二次筛未实施。