Miller_Rabin 素数测试

时间:2022-09-24 12:18:40

费马定理的逆定理几乎可以用来判断一个数是否为素数,但是有一些数是判断不出来的,因此,Miller_Rabin测试方法对费马的测试过程做了改进,克服其存在的问题。

推理过程如下(摘自*):

Miller_Rabin 素数测试

摘自另一篇博文(手动滑稽):

Miller_Rabin 素数测试

原理明白了,就直接上代码了(KuangBin大神的板子):

代码思路是,

  • Miller_Rabin()函数随机选取 s 个a,a用做“基底”
  • check() 函数是用来判断x是否等于1,也就是判断a是否是n的凭证。
  • Mul_mod()函数是 快速乘 ,求 a^t % n 之后的值是否为正负一,因为两个数直接乘的话会很大,可能会爆Long Long, 因此用快速乘边乘边mod。
  • pow_mod()函数是 快速幂 ,在刚开始第一次判断 a^(n-1) % n 时会用到。
 /* *************************************************
* Miller_Rabin 算法进行素数测试
* 速度快可以判断一个 < 2^63 的数是不是素数
*
**************************************************/
const int S = ; //随机算法判定次数一般 8 ∼ 10 就够了
// 计算 ret = (a*b)%c
//a,b,c < 2^63
long long mult_mod(long long a,long long b,long long c)
{
a %= c;
b %= c;
long long ret = ;
long long tmp = a;
while(b)
{
if(b & )
{
ret += tmp;
if(ret > c)ret -= c;//直接取模慢很多
}
tmp <<= ;
if(tmp > c)tmp -= c;
b >>= ;
}
return ret;
}
// 计算 ret = (a^n)%mod
long long pow_mod(long long a,long long n,long long mod)
{
long long ret = ;
long long temp = a%mod;
while(n)
{
if(n & )ret = mult_mod(ret,temp,mod);
temp = mult_mod(temp,temp,mod);
n >>= ;
}
return ret;
}
// 通过 a^(n − 1)=1(mod n)来判断 n 是不是素数
// n − 1 = x ∗ 2 t 中间使用二次判断
// 是合数返回 true, 不一定是合数返回 false
bool check(long long a,long long n,long long x,long long t)
{
long long ret = pow_mod(a,x,n);
long long last = ret;
for(int i = ; i <= t; i++)
{
ret = mult_mod(ret,ret,n);
if(ret == && last != && last != n - )return true;//合数
last = ret;
}
if(ret != )return true;
else return false;
}
//**************************************************
// Miller_Rabin 算法
// 是素数返回 true,(可能是伪素数)
// 不是素数返回 false
//**************************************************
bool Miller_Rabin(long long n)
{
if( n < )return false;
if( n == )return true;
if( (n&) == )return false;//偶数
long long x = n - ;
long long t = ;
while( (x&)== )
{
x >>= ;
t++;
}
srand(time(NULL));/* *************** */
for(int i = ; i < S; i++)
{
long long a = rand()%(n - ) + ;
if( check(a,n,x,t) )
return false;
}
return true;
}

Miller_Rabin 素数测试的更多相关文章

  1. 数论 - Miller&lowbar;Rabin素数测试 &plus; pollard&lowbar;rho算法分解质因数 ---- poj 1811 &colon; Prime Test

    Prime Test Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 29046   Accepted: 7342 Case ...

  2. hdu 6169 Senior PanⅡ Miller&lowbar;Rabin素数测试&plus;容斥

    Senior PanⅡ Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others) Pr ...

  3. Miller&lowbar;Rabin素数测试【学习笔记】

    引语:在数论中,对于素数的研究一直就很多,素数测试的方法也是非常多,如埃式筛法,6N±1法,或者直接暴力判(试除法).但是如果要判断比较大的数是否为素数,那么传统的试除法和筛法都不再适用.所以我们需要 ...

  4. Miller&lowbar;Rabin素数测试

    #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #inclu ...

  5. 数学:随机素数测试(Miller&lowbar;Rabin算法)和求整数素因子(Pollard&lowbar;rho算法)

    POJ1811 给一个大数,判断是否是素数,如果不是素数,打印出它的最小质因数 随机素数测试(Miller_Rabin算法) 求整数素因子(Pollard_rho算法) 科技题 #include&lt ...

  6. Miiler-Robin素数测试与Pollard-Rho大数分解法

    板题 Miiler-Robin素数测试 目前已知分解质因数以及检测质数确定性方法就只能\(sqrt{n}\)试除 但是我们可以基于大量测试的随机算法而有大把握说明一个数是质数 Miler-Robin素 ...

  7. Miller-Rabin素数测试算法(POJ1811Prime Test)

    题目链接:http://poj.org/problem?id=1811 题目解析:2<=n<2^54,如果n是素数直接输出,否则求N的最小质因数. 求大整数最小质因数的算法没看懂,不打算看 ...

  8. poj 1811 Prime Test 大数素数测试&plus;大数因子分解

    Prime Test Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 27129   Accepted: 6713 Case ...

  9. Miller-Rabbin随机性素数测试算法

    //**************************************************************** // Miller_Rabin 算法进行素数测试 //速度快,而且 ...

随机推荐

  1. Css概要与选择器,刻度单位

    目录 一.CSS3概要 1.1.特点 1.2.效果演示 1.3.帮助文档与学习 二.选择器 1.1.基础的选择器 1.2.组合选择器 1.3.属性选择器 1.4.伪类 1.5.伪元素 三.特殊性(优先 ...

  2. visio取消自动粘附

    有时候画直线的时候需要直线摆在任意位置,这个时候自动粘附就很碍事了,总是自动把你的直线给摆到粘附的特殊位置上 如何取消: 视图->视觉帮助(点右下角的小箭头)->当前活动的->取消勾 ...

  3. hard

    硬盘电路板将信号转化为电压高低,电压控制电脉冲被送到磁头,产生一个电磁.磁盘和磁头很紧密.读写都是不断扫描磁盘的过程.有操作系统负责控制文件的组织,可能在不同的块中.

  4. C&sol;C&plus;&plus; ceil和floor函数

    ceil 是“天花板" floor 是 “地板”  一个靠上取值,另一个靠下取值,如同天花板,地板. double ceil ( double x ); float ceil ( float ...

  5. in&lowbar;array严格模式和普通模式的区别

    貌似是因为test转整型变0  0和0 匹配能成功 返回真 启用严格模式发现没有这个问题

  6. PHP设计模式笔记六:数据对象映射模式 -- Rango韩老师 http&colon;&sol;&sol;www&period;imooc&period;com&sol;learn&sol;236

    数据对象映射模式 1.数据对象映射模式,是将对象和数据存储映射起来,对一个对象的操作会映射为对数据存储的操作 2.在代码中实现数据对象映射模式,我们将实现一个ORM类,将复杂的SQL语句映射成对象属性 ...

  7. Quartz 开源的作业调度框架

    Quartz 是一个开源的作业调度框架,它完全由 Java 写成,并设计用于 J2SE 和 J2EE 应用中.它提供了巨大的灵活性而不牺牲简单性.你能够用它来为执行一个作业而创建简单的或复杂的调度.本 ...

  8. 2014 HDU多校弟五场J题 【矩阵乘积】

    题意很简单,就是两个大矩阵相乘,然后求乘积. 用 Strassen算法 的话,当N的规模达到100左右就会*了 况且输入的数据范围可达到800,如果变量还不用全局变量的话连内存 ...

  9. CentOS7系统上的GPSTK示例代码调试 &amp&semi; 运行结果 &amp&semi; 心得

    下载的源码程序包中,共有16个例子,这里记录它们的调试及运行结果,尤其是哪些可用,哪些不可用,今后使用时用作参考. 总结: (1)在 18 个示例程序中,example16 和 example17 编 ...

  10. Ajax经典交互讲解

    资料: XMLHttpRequest 对象 XMLHttpRequest 对象提供了对 HTTP 协议的完全的访问,包括做出 POST 和 HEAD 请求以及普通的 GET 请求的能力.XMLHttp ...