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)≡0(modP)
或者
(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，这个数也是合数(费马小定理)
正确性
老祖宗告诉我们:joy::若p通过一次测试，则p不是素数的概率为25%
那么经过t轮测试,p不是素数的概率为\dfrac {1}{4^{t}}
我习惯用2,3,5,7,11,13,17,19这几个数进行判断
在信息学范围内出错率为0%(不带高精:joy:)
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;
}