Miller-Rabin素数测试
2024-09-02 21:52:42
Miller-Rabin素数测试
给出一个小于1e18的数,问它是否为质数?不超过50组询问。hihocoder
我是真的菜,为了不误导他人,本篇仅供个人使用。
首先,一个1e18的数,朴素\(O(\sqrt{n})\)素数判定肯定爆炸。怎么办呢?
我们知道,对于素数p,只要a不是p的倍数,一定有\(a^{p-1}=1\mod p\)。那么,我们是不是可以选出某些a,对于要判定的数p,看看他是否满足以a为底的费马小定理,以此来判定质数呢?答案是基本可以。
但是很不巧,有一类合数,以任何小于它们的质数为底进行判定,结果都是正确的。它们叫做伪素数。怎么排除伪素数的情况呢?有个叫做二次探测定理的东西:若\(x^2=1\mod p\),那么\(或x=1或-1\mod p\)。
假设\(a^{x-1}=1\mod p\)成立。如果x-1为奇数,就不再判定下去。否则,根据二次探测定理,还可以继续去判定\(或a^{\frac{x-1}{2}}=1或-1\mod p\)是否成立。如果它不等于1或-1,就返回false。如果它等于-1,就返回true。如果它等于1,就继续判定下去。反正,只要x-1为偶数,并且\(a^{x-1}=1\mod p\),就可以一直判定。这样就可以把那些伪素数排除掉了。这就叫做miller-rabin素数测试。据说选前7个质数作为a,在1e18内也只有两三个会被miller-rabin判定成素数的合数。
#include <cstdio>
using namespace std;
typedef long long LL;
const LL m=7, a[m]={2, 3, 5, 7, 11, 13, 17};
LL n, p;
LL fmul(LL a, LL b, LL p){ //将b分解为二进制,返回a*b%p
LL ans=0;
for (; b; b>>=1, a+=a, a%=p)
if (b&1) ans+=a, ans%=p;
return ans;
}
LL fpow(LL a, LL x, LL p){
LL ans=1, base=a;
for (; x; x>>=1, base=fmul(base, base, p))
if (x&1) ans=fmul(ans, base, p);
return ans;
}
bool MR(LL a, LL x, LL p){ //判断是否a^x=1或p-1 (mod p),且mr下去也成立
LL t=fpow(a, x, p);
if (t!=1&&t!=p-1) return false;
if (t==1&&x&1||t==p-1) return true;
return MR(a, x>>1, p);
}
bool isprime(LL p){
if (p&1==0) return false;
for (LL i=0; i<m; ++i){
if (p==a[i]) return true; //互质时费马小定理才成立
if (fpow(a[i], p-1, p)!=1) return false;
if (!MR(a[i], (p-1)>>1, p)) return false;
}
return true;
}
int main(){
scanf("%lld", &n);
while (n--){
scanf("%lld", &p);
puts(isprime(p)?"Yes":"No");
}
return 0;
}
最新文章
- iOS-自动布局Autolayout(原创)
- Android开发者必须掌握的知识技能清单
- Web Service(一) 基础学习
- What is the difference Apache (Http Server) and Tomcat (Servlet Container)
- Android开发之隐式Intent中Intent-filter的三个属性-action,category,data
- 07_MyBatis原始的Dao编写方法
- python字符串转义与正则表达式特殊字符转义
- hadoop--安装1.2.1版本
- 基于laravel5.4 vue 和vue-element搭建的单页面后台CMS
- 如何生成CA证书
- js 获取 最近七天 30天 昨天的方法 -- 转
- java保留小数-抄网上的
- 【转】Python3 操作符重载方法
- noip 2018游记
- 多表查询、可视化工具、pymysql模块
- Django MTV模式详解
- JS 事件 Event
- 0_Simple__UnifiedMemoryStreams
- python读取文件另存为
- printf in KEIL C51