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素数テストの実装コードは以下の通りである.
フェルマの小さな定理から分かるように、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
#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;
}