何为Miller Rabin算法
首先看一下度娘的诠释(如果您懒得读直跨越了就算可反正也尚无啥乱用:joy:)
Miller-Rabin算法是当下主流的根据概率的素数测试算法，在构建密码安全体系中占据主要的身价。通过比较各种素数测试算法和针对性Miller-Rabin算法进行的缜密研究，证明在电脑被构建密码安全系时，
Miller-Rabin算法是到位素数测试的最佳选项。通过对Miller-Rabin 算
法底层运算的优化，可以得到比较过去落实还好的性质。[1] 随着信息技术的发展、网络的推广和电子商务的拓，
信息安全逐步显示出了那重要。信息的泄密、伪造、篡改
等题材会于信息的官方拥有者带来重要的损失。在微机被构建密码安全系可以提供4种植最中心的护卫信息安全的服
务：保密性、数据完整性、鉴别、抗抵赖性，从而得以挺大
程度达护用户的多寡安全。在密码安全系统中，公开密钥
算法在密钥交换、密钥管理、身份证明等问题的拍卖达成无与伦比有效，因此于方方面面体系中占重要之身份。目前底公开密钥
算法大部分基于大整数分解、有限域上之离散对数问题和椭
圆曲线上的离散对数问题，这些数学难题的构建大部分还需
要杀成一栽超大的素数，尤其当藏的RSA算法中，生成的素数的质量对系的安全性产生充分十分的熏陶。目前大素数的生
成，尤其是任意大素数的变通主要是动素数测试算法，本
文主要针对时主流的Miller-Rabin 算法进行全面系统的剖析
和钻研，并针对那实现进行了优化
说白了Miller
Rabin算法在信息学奥赛中之动即一样句话:
认清一个屡是否是素数
何为Miller Rabin算法
先是看一下度娘的解释(如果你懒得读直跨越了就是可反正也没啥乱用:joy:)
Miller-Rabin算法是时主流的冲概率的素数测试算法，在构建密码安全系受到占有重要之身价。通过比较各种素数测试算法和对Miller-Rabin算法进行的细致研究，证明在计算机被构建密码安全系统时，
Miller-Rabin算法是瓜熟蒂落素数测试的极品选项。通过对Miller-Rabin 算
法底层运算的优化，可以获得比较往年落实还好的性。[1] 随着信息技术的提高、网络的普及以及电子商务的拓展，
信息安全逐步显示有了那主要。信息之泄密、伪造、篡改
等问题会见被信息之法定拥有者带来重要的损失。在电脑中构建密码安全系统可以供4栽最中心的保安信息安全之服
务：保密性、数据完整性、鉴别、抗抵赖性，从而可以老大
程度及保护用户之数安全。在密码安全系受到，公开密钥
算法在密钥交换、密钥管理、身份认证等题材的处理上最好有效，因此在一切系统中占据举足轻重的身价。目前之公开密钥
算法大部分根据大整数分解、有限域上的离散对数问题和椭
圆曲线上之离散对数问题，这些数学难题的构建大部分且需
要十分成一栽超大的素数，尤其当经的RSA算法中，生成的素数的品质对网的安全性产生死十分之震慑。目前大素数的生
成，尤其是自由大素数的变主要是以素数测试算法，本
文主要对当前主流的Miller-Rabin 算法进行宏观系统的辨析
和研究，并针对性该落实进行了优化
说白了Miller
Rabin算法在信息学奥赛中之下就是同样句话:
判定一个屡是否是素数
定理
Miller
Rabin算法的依据是费马小定理:
$$a^{p-1}\equiv 1\left(
modP\right)$$
证明：
特性1：$p-1$只整数$a,2a,3a,…(p-1)a$中从不一个凡$p$的翻番
特性2：$a,2a,3a,…(p-1)a$中没有其他两只同余与模$p$的
就此$a,2a,3a,…(p-1)a$对模$p$的同余既非呢零星，也尚未点儿单及余平
于是，这$p-1$个数模$p$的同余一定是$a,2a,3a,…(p-1)a$的有一样种排列
即$a,2a,3a,…(p-1)a \equiv
{1,2,3,…,p-1}! (mod p)$
化简为
$a^{p-1}*(p-1)! \equiv {p-1}! (mod
p)$
据悉威尔逊定律可知$(p-1)!$与$p$互质，所以又横去$(p-1)!$
即得到$a^{p-1}\equiv 1\left(
modP\right)$
那是未是当一个数$p$满足任意$a$使得$a^{p-1}\equiv
1\left( modP\right)$成立的时节她就是素数呢？
在费马小定理被证明后底不得了丰富一段时间里，人们都认为就是深明显的，
而是毕竟来一样天，人们被有了反例 ,推翻了这个结论
立是否代表利用费马小定理的思考去判断素数的思索便是荒谬的啊？
答案是必之。
而倘若我们可人工的管出错率降到大小为？
遵，对于一个屡，我们出$99.99999$%的几乎率做出科学判断，那这种算法不为非常不错越么？
于是Miller Rabin算法诞生了！
第一介绍一下次之不良探测定理
若$p$为素数,$a^{2}\equiv 1\left(
modP\right)$，那么$a\equiv \pm 1\left( modP\right)$
证明
$a^{2}\equiv 1\left(
modP\right)$
$a^{2}-1\equiv 0\left(
modP\right)$
$(a+1)*(a-1)\equiv 0\left(
modP\right)$
那么
$(a+1)\equiv 0\left(
modP\right)$
或者
$(a-1)\equiv 0\left(
modP\right)$
(此处可因唯一分解定理证明)
即
$a\equiv \pm 1\left(
modP\right)$
夫定律和素数判定来啊用吗？
先是，根据Miller Rabin算法的进程
使需要判定的高频是$p$
(博主乱入:以下内容较肤浅,请仔细了解:joy:)
我们把$p-1$分解为$2^k*t$的形式
接下来轻易选一个数$a$，计算出$a^t mod
p$
受该相连的$*2$，同时重组二软探测定理进行判定
如我们$*2$后底数$mod p ==
1$，但是前的数$mod p != \pm 1$
那是累便是合数(违背了次不成探测定理)
诸如此类就$k$次，最后收获的往往便是$a^{p-1}$
这就是说只要最终计算起之累累不也$1$，这个数也是合数(费马小定理)
定理
Miller
Rabin算法的基于是费马小定理:
$$a^{p-1}\equiv 1 \pmod P$$
证明：
性能1：$p-1$个整数$a,2a,3a,…(p-1)a$中从不一个凡$p$的倍数
性2：$a,2a,3a,…(p-1)a$中无其余两个同余与模$p$的
所以$a,2a,3a,…(p-1)a$对模$p$的同余既未呢零星，也绝非简单独及余相同
为此，这$p-1$个数模$p$的同余一定是$a,2a,3a,…(p-1)a$的某个同种植排列
即$a*2a*3a*…*(p-1)a \equiv
{1*2*3*…*(p-1)} \pmod p$
化简为
$a^{p-1}*(p-1)! \equiv {p-1}! \pmod
p$
基于威尔逊定律可知$(p-1)!$与$p$互质，所以又横去$(p-1)!$
即得到$a^{p-1}\equiv 1 \pmod P$
那么是休是当一个数$p$满足任意$a$使得$a^{p-1}\equiv
1 \pmod P$成立的时节她就是是素数呢？
在费马小定理被验证后底坏丰富一段时间里，人们都觉得就是充分显著的，
然而毕竟发生一样天，人们吃有了反例 ,推翻了这个结论
立是否意味利用费马小定理的考虑去判断素数的合计便是一无是处的也？
答案是大势所趋的。
可是若我们可以人工的将出错率降到非常小为？
随，对于一个再三，我们发$99.99999$%之几带领做出科学判断，那这种算法不也酷美妙越么？
乃Miller Rabin算法诞生了！
第一介绍一下次之不良探测定理
若$p$为素数,$a^{2}\equiv 1 \pmod
P$，那么$a\equiv \pm 1 \pmod P$
证明
$a^{2}\equiv 1 \pmod P$
$a^{2}-1\equiv 0 \pmod P$
$(a+1)*(a-1)\equiv 0 \pmod P$
那么
$(a+1)\equiv 0 \pmod P$
或者
$(a-1)\equiv 0 \pmod P$
(此处可因唯一分解定理证明)
即
$a\equiv \pm 1 \pmod P$
夫定律和素数判定来什么用啊？
第一，根据Miller Rabin算法的经过
若是需要看清的再三是$p$
我们把$p-1$分解为$2^k*t$的形式
当$a$是素数，有$a ^ {2^k * t} \equiv 1
\pmod p$
下一场轻易挑选一个数$a$，计算出$a^t \pmod
p$
叫那个相连的自乘，同时整合二涂鸦探测定理进行判断
一经我们自乘后底数$\pmod p =
1$，但是之前的数$\pmod p \not = \pm 1$
这就是说这个数就是合数(违背了第二不良探测定理)
这么就$k$次，最后抱的反复便是$a^{p-1}$
那只要最终计算产生的再三不也$1$，这个数也是合数(费马小定理)
正确性
老祖宗告诉我们:joy::若$p$通过一致不善测试，则$p$不是素数的票房价值为$25$%
那通过$t$轮测试,$p$不是素数的票房价值为$\dfrac
{1}{4^{t}}$
自习惯用$2,3,5,7,11,13,17,19$这几个数进行判定
每当信息学范围外出错率为$0$%(不牵动大精:joy:)
正确性
老祖宗告诉我们，若$p$通过平等浅测试，则$p$不是素数的几率也$25$%
那么通过$t$轮测试,$p$不是素数的几率也$\dfrac
{1}{4^{t}}$
自我习惯用$2,3,5,7,11,13,17,19$这几只数进行判定
每当信息学范围外出错率为$0$%(不牵动大精)
code
瞩目在进展素数判断的时刻需要用快速幂。。
斯应该比较简单，就非仔细讲了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define LL long long
using namespace std;
const LL MAXN=2*1e7+10;
const LL INF=1e7+10;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline LL read()
{
char c=nc();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
return x*f;
}
LL fastpow(LL a,LL p,LL mod)
{
LL base=1;
while(p)
{
if(p&1) base=(base*a)%mod;
a=(a*a)%mod;
p>>=1;
}
return base;
}
LL num[]= {2,3,5,7,11,13,17,19};
bool Miller_Rabin(LL n)
{
if (n==2) return 1;
if((n&1)==0||n==1) return false;
for (LL i=0; i<8; i++) if (n==num[i]) return 1;
LL temp=n-1,t=0,nxt;
while((temp&1)==0) temp>>=1,t++;
for(LL i=0;i<8;i++)
{
LL a=num[i];
LL now=fastpow(a,temp,n);
nxt=now;
for(LL j=1;j<=t;j++)
{
nxt=(now*now)%n;
if(nxt==1&&now!=n-1&&now!=1) return false;
now=nxt;
}
if(now!=1) return false;
}
return true;
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
LL N=read(),M=read();
while(M--)
{
LL opt=read();
if(Miller_Rabin(opt)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
code
顾在进展素数判断的时刻要采取快速幂。。
斯当比较简单，就未过细讲了
#include<cstdio>
#define LL long long
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, Test[10] = {2, 3, 5, 7, 11, 13, 17};
int pow(int a, int p, int mod) {
int base = 1;
for(; p; p >>= 1, a = (1ll * a * a) % mod)
if(p & 1) base = (1ll * base * a) % mod;
return base % mod;
}
bool Query(int P) {
if(P == 1) return 0;
int t = P - 1, k = 0;
while(!(t & 1)) k++, t >>= 1;
for(int i = 0; i < 4; i++) {
if(P == Test[i]) return 1;
LL a = pow(Test[i], t, P), nxt = a;
for(int j = 1; j <= k; j++) {
nxt = (a * a) % P;
if(nxt == 1 && a != 1 && a != P - 1) return 0;
a = nxt;
}
if(a != 1) return 0;
}
return 1;
}
main() {
N = read(); M = read();
while(M--) puts(Query(read()) ? "Yes" : "No");
}