【数学】【ふるい数】Miller-Rabin素性テスト学習ノート

Miller-Rabinは効率的なランダムアルゴリズムであり、1つの数$p$が素数であるかどうかを検出し、最悪の時間複雑度は$log^3 p$であり、正解率は約$1-4^{-k}$、$k$が検査回数である.

一、出所

Miller‐RabinはMillerとRabinの2人がFerma小定理の逆定理,すなわちFerma試験に基づいて最適化したものである.フェルマの小さな定理は$$a^{p-1}equiv 1(mod p)$$
$p$が素数である場合にフェルマの小さな定理が成立することを知っていますが、もし1つの数がフェルマの小さな定理を満たすならば、それはきっと素数ですか?この数が肥えた腸が小さい場合、それは満たされることが分かったが、ある日341という数は2をベースとしたフェルマの小さな定理を満たし、$2^{340}equiv 1(mod 341)$を満たすことが分かったが、それは合数$(341=11times 31)$であった.
この時、MillerとRabinはこのフェマテストというものを改善しました......
誰が証明するんだ?

にじたんさのていり

二次探知定理というものがあり、フェマの小さな定理の正確性を効果的に向上させることができます.素数$p$に対して正の整数$xがある場合

三、Miller-Rabin素性試験

二次プローブの定理があり,341の2をベースとしたFerma試験を行ってみた.$2^{340}equiv 1(mod 341)$,341が素数であれば,二次プローブ定理,すなわち$2^{170}equiv 1(mod 341)$も満たす.170は偶数であり,二次検出の定理を継続することができる.このとき、$2^{85}equiv 32(mod 341)$が涼しくなり、二次探査の定理が通らないため、341は素数ではありません.
また、フェルマの小さな定理には底が要求されていないため、2を底にして網漏れの魚を見逃すに違いない.私たちはもっと数を底にしなければならない.そうすれば、判断の正確性を高めることができる.しかし、この底には素数を選んだほうがいい(なぜか、答えの模数とほとんど同じかもしれないが...).正確性を保証します.また、このアルゴリズムを学ぶと、ネット上で不思議な結論が書かれます.例えば、3つの特定のベース$2,7,61$を選択すると、$4759123141$未満のすべての素数のテストを通過することができますが、$latex 2,3$をベースにすると、$1373653$以内のテストを通過することができます.そのため、多くの人がランダムな数をベースにするのが好きで、テーマが与える質数も違います.これは運に頼っています.しかし、上記の分析では、その誤り率は約$4^{-k}$しかないので、出題者はあなたの底数を知らない場合、正確率は特に高いと考えられています.

四、まとめ

Miller-Rabinは肥えた腸で効率的で、書くのも便利です.問題の中であなたの線に$10^7$の数をふるい出すほど変態していません.特にカード空間の問題では、空間を含む多くの資源が浪費されています.この時Milller-Rabinは良い選択です.

五、Code（luoguリニアスクリーンテンプレート）

ここの範囲は$10^7$なので、上の特定の底数$2,7,61$で通過できます

#include
#include
long long qpow(long long x,long long y,long long p)// 
{
    long long ans=1,m=x;
    while(y)
    {
        if(y&1)
            ans*=m;
        ans%=p;
        m*=m;
        m%=p;
        y>>=1;
    }
    return ans;
}
bool check(long long x,long long y,long long p)// 
{
    long long tmp=qpow(x,y,p);
    if(tmp!=1&&tmp!=p-1)
        return false;
    if(tmp==p-1)
        return true;
    if(tmp==1&&(y&1))
        return true;
    return check(x,y>>1,p);
}
bool millerrabin(long long x)
{
    if(x<=1)
        return false;
    if(x==2||x==7||x==61||(check(2,x-1,x)&&check(7,x-1,x)&&check(61,x-1,x)))// ， qwq
        return true;
    return false;
}
int main()
{
    int n,m;
    long long u;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&u);
        if(millerrabin(u))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

　　
 
転載先:https://www.cnblogs.com/wjyyy/p/note1.html