【テンプレート】素数試験(Miller-Rabin試験)

ベース素数テストテンプレート
大数の素性判断に対しては,現在Miller‐Rabinアルゴリズムが最も広く応用されている.一般的な基数は依然としてランダムに選択されているが、測定対象数があまり大きくない場合、テスト基数を選択するにはいくつかのテクニックがある.例えば、被測定数が4759123141未満であれば、3つの底数a[]={2,7,61}をテストするだけで十分である.もちろん、テストが多ければ多いほど、正しい範囲も大きくなります.最初の7つの素数a[]={2,3,5,7,11,13,17}でテストを行うと、3415500712728320を超えない数はすべて正しいです.a[]={2,3,7,61242551}を基数として選択すると、10^16内の唯一の強い擬似素数は46856248255981である.このようないくつかの結論はMiller‐RabinアルゴリズムをOIにおいて非常に実用的にした.通常,Miller−Rabin素性試験の正解率は許容可能であり,k個の底数をランダムに選択して試験アルゴリズムを行うミス率は約4^(-k)であると考えられる.
tip:1は判断できず、自分でfalseと特判するしかありません!

#include
using namespace std ;
typedef long long ll;
ll pow_mod(ll a,ll b,ll r)
{
    ll ans=1,buff=a;
    while(b)
    {
        if(b&1)
            ans=(ans*buff)%r;
        buff=(buff*buff)%r;
        b>>=1;
    }
    return ans;
}

bool test(ll n,ll a,ll d)
{
    if(n==2)return true;
    if(n==a)return false;
    if(!(n&1))return false;
    while(!(d&1))d>>=1;
    ll t=pow_mod(a,d,n);
    while(d!=n-1&&t!=n-1&&t!=1)
    {
        t=t*t%n;
        d<<=1;
    }
    return t==n-1||(d&1)==1;// t n-1， t=1
}

bool isprime(ll n)
{
    int a[]={2,3,5,7};      // 
    for(int i=0;i<=3;i++)
    {
        if(n==a[i])return true;
        if(!test(n,a[i],n-1))return false;
    }
    return true;
}
int main()
{ 
    int t;
    ll n;  
    for(cin>>t;t;t--)
    {
        cin>>n;
        cout<"Yes":"No")<<endl;
    }
    return 0; 
}

ps:上記のアルゴリズムのべき乗演算はlonglongタイプであり、longlong×longlongは必ずオーバーフロー現象が発生します.javaの大きな整数がなく、手にも大きな整数乗算テンプレートがない場合は、オーバーフローを避ける小さなテクニックがあります.乗算を加算に変更し、上のコードを加算します.

ll pow_mod(ll a,ll b,ll r)
{
    ll ans=1,buff=a;
    while(b)
    {
        if(b&1)
            ans=(ans*buff)%r;
        buff=(buff*buff)%r;
        b>>=1;
    }
    return ans;
}

変更後:

ll mod_mul(ll a,ll b,ll n)
{
    ll res=0;
    while(b)
    {
        if(b&1)
            res=(res+a)%n;
        a=(a+a)%n;
        b>>=1;
    }
    return res;
}

ll pow_mod(ll a,ll b,ll n)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=mod_mul(res,a,n);
        a=mod_mul(a,a,n);
        b>>=1;
    }
    return res;
}

 
転載先:https://www.cnblogs.com/kannyi/p/9569506.html