Miller-Rabin素数テスト

1906 ワード

比較的大きな数が素数であるか否かを判断する場合,従来の試除法とふるい法は明らかに適用されなくなり,確率型素数判定法であるMiller−Rabin素数試験を導入した.
フェルマの小さな定理から分かるように、nが素数でaが整数であれば、a^n≡a(mod n)を満たす.aが上式を満たさない場合、nは合数である.これにより、aを正の整数とし、nが合数でa^n≡a(mod n)を満たす場合、nをaをベースとする偽素数と呼ぶ.
Miller-Rabin素数試験は、nが素数でgcd(a,n)=1である場合、a^(n-1)≡1(mod n).a^(n−1)≡1(mod n)(aがnより任意に小さい正の整数)であれば、nを素数と近似し、複数の底を取って試験を行い、回数が多ければ多いほど、nが素数である確率が大きくなる.
定義カマイケル数:一つの合数nは、gcd(b,n)=1を満たすすべての正の整数bに対してb^(n-1)≡1(mod n)が成立する場合、カマイケル数と呼ぶ.
カマイケル数によるMiller-Rabin試験の誤りを排除するために,pが素数で0改良されたMiller-Rabin素数テストの実装コードは以下の通りである.
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
#define N 10
typedef long long LL;
LL random(LL n)
{
    return (LL)((double)rand()/RAND_MAX*n+0.5);
}
LL multi(LL a,LL b,LL m) // a*b%m
{
    LL ret=0;
    while(b)
    {
        if(b&1) ret=(ret+a)%m;
        b>>=1;
        a=(a<<1)%m;
    }
    return ret;
}
LL quick_mod(LL a,LL b,LL m) // a^b%m
{
    LL ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=multi(ans,a,m);
            b--;
        }
        b>>=1;
        a=multi(a,a,m);
    }
    return ans;
}
bool miller_rabin(LL n)
{
    if(n==2) return true;
    if(n<2||!(n&1)) return false;
    LL m=n-1;
    int k=0;
    while((m&1)==0)
    {
        k++;
        m>>=1;
    }
    for(int i=0; i<N; i++)
    {
        LL a=rand()%(n - 1)+1;
        LL x=quick_mod(a,m,n);
        LL y=0;
        for(int j=0;j<k;j++)
        {
            y=multi(x,x,n);
            if(y==1&&x!=1&&x!=n-1) return false;
            x=y;
        }
        if(y!=1) return false;
    }
    return true;
}
int main()
{
    LL n;
    while(cin>>n)
      if(miller_rabin(n)) puts("yes");
      else puts("no");
    return 0;
}