Miller Robbin测试模板（无讲解）

95 阅读 0 评论 63 点赞

我是靠谱客的博主务实糖豆，最近开发中收集的这篇文章主要介绍Miller Robbin测试模板（无讲解），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

想着费马定理和二次探测定理就能随手推了。

做一次是log ²n的。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long int ll;
 4 ll T,n;
 5 ll qpow(ll x,ll y,ll mod)
 6 {
 7
ll ans=1,base=x;
 8
while(y)
 9 
{
10
if(y&1)ans=ans*base%mod;
11
base=base*base%mod;
12
y>>=1;
13 
}
14
return ans;
15 }
16 bool check(ll p,ll a,ll m,ll q)
17 {
18
if(a==p)return 1;
19
ll base=qpow(a,m,p);
20
ll last=base;
21
for(int i=1;i<=q;++i)
22 
{
23
base=base*base%p;
24
if(base==1&&last!=1&&last!=p-1)return 0;
25
last=base;
26 
}
27
if(base!=1)return 0;
28
return 1;
29 }
30 bool miller(ll n)
31 {
32
if(n==1)return 0;
33
if(n==2)return 1;
34
if(n%2==0)return 0;
35
ll x=n-1,sum=0;
36
while(x%2==0){++sum;x/=2;}
37
if(!check(n,2,x,sum))return 0;
38
if(!check(n,3,x,sum))return 0;
39
if(!check(n,5,x,sum))return 0;
40
if(!check(n,7,x,sum))return 0;
41
if(!check(n,11,x,sum))return 0;
42
if(!check(n,13,x,sum))return 0;
43
if(!check(n,17,x,sum))return 0;
44
return 1;
45 }
46 int main()
47 {
48
ios::sync_with_stdio(false);
49
cin>>T;
50
while(T--)
51 
{
52
cin>>n;
53
cout<<n<<" "<<(miller(n)==1?"Yes":"No")<<endl;
54 
}
55
return 0;
56 }