首页 📚学习笔记

Miller-Rabin

当一个数特别大,无法用$\mathcal O(\sqrt n)$的时间复杂度判断它是不是质数时,我们就可以有几率地用$Miller-Rabin$判断出它是否是质数


费马小定理

$a^{p-1}≡1(mod \quad p)$

当$p$为质数且$p,a$互质的时候费马小定理成立

那如果满足上式的话能否知道$p$是不是质数呢?答案是不一定

当$a=2,p=341$是,虽然满足上式,但是$341=11*31$

啥玩意儿啊,咋回事儿啊,那咋整啊


二次探测定理

对于质数$p$,
如果有一个$x<p$使得$x^2≡1(mod\quad p)$,那么

$$ \begin{align} x^2-1&≡0(mod\quad p)\\ (x-1)(x+1)&≡0(mod\quad p)\\ \end{align} $$

$∴p|(x+1)(x-1)$
$x_1=1,x_2=p-1$


回到刚才的$2^{340}≡1(mod\quad 341)$

如果$341$是质数,他也应该满足二次探测定理

因为$2^{340}≡(2^{170})^2≡1(mod\quad 341)$

所以$2^{170}≡±1(mod\quad 341)$($-1$≡p-1=340)

也就是$2^{170}≡1(mod\quad 341)$,而$170$还是个偶数,可以继续进行二次探测定理

因为$2^{85}≡32(mod\quad 341)$,它就$gg$了,没有通过二次探测定理,所以341不是个素数。

但是这样还不是很保险,费马小没有规定底数,所以我们可以多找点其他的数来为底,正确性就会提高,不过最好选质数

一般选$3$个特定的底$2,7,61$,就可以通过小于$4759123141$的所有素数的测试.你也可以随机数碰碰运气,只要不被大佬膜,一般$rp$是能过的

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p,m;
long long qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%p;
        x=x*x%p;
        y>>=1;
    }
    return res;
}
bool check(int x,int y){
    int ans=qpow(x,y);
    if(ans!=1&&ans!=p-1)return false;
    if(ans==p-1)return true;
    if(ans==1&&y%2==1)return true;
    return check(x,y>>1);
}
bool is_prime(int x){
    if(x<=1)return false;
    if(x==2||x==7||x==61||check(2,x-1)&&check(7,x-1)&&check(61,x-1))
        return true;
    return false;
}
signed main(){
    scanf("%lld",&m);
    while(m--){
        scanf("%lld",&p);
        if(is_prime(p))puts("YES");
        else puts("NO");
    }
    return 0;
}



文章评论