星星之火OIer：素数判断——Miller_Rabin——普通判断——Miller Rabin素数测试法

116 阅读 0 评论 77 点赞

我是靠谱客的博主大意发夹，这篇文章主要介绍星星之火OIer：素数判断——Miller_Rabin——普通判断——Miller Rabin素数测试法，现在分享给大家，希望可以做个参考。

在这一讲中，我们来看一下如何判断一个素数

常用的有 $2$ 种

——普通判断

——Miller Rabin素数测试法

算法前置：：

算法流程：：

代码：：

$o(sqrt{n})=o(n^frac{1}{2})$ ——普通判断

从 $2$ 到 $sqrt{n}$ 依次判断 $n % i$ 是否等于 $0$

代码如下：：

复制代码

1
2
3
4
5
6
for(int i=2;i<=int(sqrt(n));i++)
if(n%i==0) {
puts("Unprime");//将就看到起，我也不晓得怎么说了
return 0;
}
puts("Prime");

这是很简单的

$o(sqrt{sqrt{n}})=o(n^frac{1}{4})$ ——Miller Rabin素数测试法

这是一个可以检测 $rp$ 的算法

因为这是基于随机算法而来的素数测试法

算法前置：：

费马小定理：若 $a$ 是整数， $p$ 是质数，且 $a%p!=0$ ，则 $a^{p-1}equiv 1(mod p)$ ，但反过来不一定成立，即如果 $a^{p-1}equiv 1(mod p)$ 且 $a,p$ 互质不能退出 $p$ 为质数，但这种数是极少见的
二次探测定理：若 $p$ 是质数，且 $0<x<p$ ，则方程 $x^2-1equiv 1(mod p)$ 的解为 $x=1$ 或 $x=p-1$
模运算： $(a*b)%n=(a%n*b%n)%n$
快速幂、快速积：运用二分的思想，快速求出 $a^b$ 和 $a*b$

算法流程：：

判断 $n$ 是不是2，如果是，返回 $true$
判断 $n$ 是否小于2或者 $n%2==0$ ，如果是，返回 $false$
令 $n-1=u*2^t$ 并求出 $u,t$ ，其中 $u$ 是奇数
令 $x=(a^u)%n$
然后是 $t$ 次循环，每次循环都让 $y=(x^2)%n,x=y$ ，这样t次循环之后 $x=a^{u*2^t}=a^{n-1}$
因为根据二次探测定理定理，如果 $x!=1||x!=n$ ，那么 $n$ 肯定不是质数，返回 $false$
然后又可以用费马小定理，若 $x!=1$ ，则 $n$ 也不是质数
然鹅因为Miller_Rabin算法的正确率只有 $75%$ 左右，所以要循环 $k$ 次， $k$ 请自取，算法错误率为 $frac{1}{4^k}$
然后就看 $rp$ 了

更多详细的解释请看代码，谢谢

代码：：

复制代码

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define il inline
#define rt return
#define bl bool
#define vd void
il vd read(ll &x) {
x=0;
ll f=1;
char s=getchar();
while(s<'0'||s>'9') {
if(s=='-')
f=-1;
s=getchar();
}
while(s>='0'&&s<='9') {
x=x*10+s-48;
s=getchar();
}
x*=f;
}
il vd pr(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9)
pr(x/10);
putchar(x%10+48);
}//快读快输不解释
il ll ksc(ll a,ll b,ll n) {//快速幂和快速积请看作者的另一篇博客
ll ans=0;
while(b) {
if(b&1)
ans=(ans+a)%n;
a=(a<<1)%n;
b>>=1;
}
rt ans;
}
il ll ksm(ll a,ll b,ll n) {
ll ans=1;
while(b) {
if(b&1)
ans=ksc(ans,a,n);
a=ksc(a,a,n);
b>>=1;
}
rt ans;
}
il bl miller_rabin(ll n) {//Miller_Rabin算法
ll a,b,x,y,u,t;
if(n==2)//看n是否为2
rt 1;//为2就是质数
else if(n<2||!(n&1))//小于2或是2的倍数
rt 0;//不是质数
for(t=0,u=n-1;!(u&1);t++,u>>=1);//求出u和t
for(ll i=0;i<20;i++) {//这个20是可以想开多大就开多大的/*只要不超时*/
a=rand()%(n-2)+2;//随机生成一个数
x=ksm(a,u,n);//快速幂
for(ll j=0;j<t;j++) {
y=ksc(x,x,n);//快速积
if(y==1&&x!=1&&x!=n-1)//二次探测定理
rt 0;//不是质数
x=y;//更新
}
if(x!=1)//费马小定理
rt 0;//不是质数
}
rt 1;//有很大可能是质数
}
ll t,n,a;
int main() {
srand((unsigned)time(NULL));
read(t);
while(t--) {
read(n);
if(miller_rabin(n))
puts("YES");
else
puts("NO");
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define il inline
#define rt return
#define bl bool
#define vd void
il vd read(ll &x) {
x=0;
ll f=1;
char s=getchar();
while(s<'0'||s>'9') {
if(s=='-')
f=-1;
s=getchar();
}
while(s>='0'&&s<='9') {
x=x*10+s-48;
s=getchar();
}
x*=f;
}
il vd pr(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9)
pr(x/10);
putchar(x%10+48);
}//快读快输不解释
il ll ksc(ll a,ll b,ll n) {//快速幂和快速积请看作者的另一篇博客
ll ans=0;
while(b) {
if(b&1)
ans=(ans+a)%n;
a=(a<<1)%n;
b>>=1;
}
rt ans;
}
il ll ksm(ll a,ll b,ll n) {
ll ans=1;
while(b) {
if(b&1)
ans=ksc(ans,a,n);
a=ksc(a,a,n);
b>>=1;
}
rt ans;
}
il bl miller_rabin(ll n) {//Miller_Rabin算法
ll a,b,x,y,u,t;
if(n==2)//看n是否为2
rt 1;//为2就是质数
else if(n<2||!(n&1))//小于2或是2的倍数
rt 0;//不是质数
for(t=0,u=n-1;!(u&1);t++,u>>=1);//求出u和t
for(ll i=0;i<20;i++) {//这个20是可以想开多大就开多大的/*只要不超时*/
a=rand()%(n-2)+2;//随机生成一个数
x=ksm(a,u,n);//快速幂
for(ll j=0;j<t;j++) {
y=ksc(x,x,n);//快速积
if(y==1&&x!=1&&x!=n-1)//二次探测定理
rt 0;//不是质数
x=y;//更新
}
if(x!=1)//费马小定理
rt 0;//不是质数
}
rt 1;//有很大可能是质数
}
ll t,n,a;
int main() {
srand((unsigned)time(NULL));
read(t);
while(t--) {
read(n);
if(miller_rabin(n))
puts("YES");
else
puts("NO");
}
}