Miller-Rabin(素数テスト)
3770 ワード
フェルマの小さい定理と二次探知の定理を用いて素数のテストを行う
方法2:
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
__int64 mod_exp(__int64 a, __int64 b, __int64 n) // (a^b) mod n
{
__int64 d = 1;
a = a % n;
while (b) {
if (b & 1) d = a*d%n;
a = a*a%n;
b = b >> 1;
}
return d;
}
bool Wintess(__int64 a, __int64 n) // a n Miller
{
__int64 m, x, y;
int i, j = 0;
m = n - 1;
while (m % 2 == 0) // (n-1)=m*(2^j) j m,j=0 m=n-1, 2 n
{
m = m >> 1;
j++;
}
x = mod_exp(a, m, n);
for (i = 1; i <= j; i++) {
y = mod_exp(x, 2, n);
if ((y == 1) && (x != 1) && (x != n - 1)) //
return true; // true ,n
x = y;
}
if (y != 1) return true;
return false;
}
bool miller_rabin(int times, __int64 n) // n times Miller
{
__int64 a;
int i;
if (n == 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
srand(time(NULL));
for (i = 1; i <= times; i++) {
a = rand() % (n - 2) + 2;
if (Wintess(a, n)) return false;
}return true;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
if(miller_rabin(5,n)) cout<<n<<" is a prim"<<endl;
else cout<<n<<" is not a prim"<<endl;
}return 0;
}
方法2:
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef __int64 L;
void power(L a,L p,L n,L& result,bool& composite)
{
L x;
if(p==0)
{
result=1;
return;
}
power(a,p/2,n,x,composite);
result=(x*x)%n;
if(result==1&&(x!=1)&&(x!=n-1)) composite=true;
if(p&1) result=(result*a)%n;
}
bool Miller_Rabin(L n,L times)
{
L a,result;
bool composite=false;
srand(time(NULL));
for(L i=1;i<=times;++i)
{
a=rand()%(n-3)+2;
power(a,n-1,n,result,composite);
if(composite||result!=1) return false;
}
return true;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
if(Miller_Rabin(n,5)) cout<<n<<" is a prim"<<endl;
else cout<<n<<" is not a prim"<<endl;
}return 0;
}
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef long long L;
void power(L a,L p,L n,L& result ,bool& flag)
{
L x;
if(p==0)
{
result=1;
return;
}
power(a,p/2,n,x,flag);
result=(x*x)%n;//
if((result==1)&&(x!=1)&&(x!=n-1)) flag=true;
if(p&1) result=(result*a)%n;
}
int main()
{
int T;
cin>>T;
while(T--){
int times;
L n;
cin>>n>>times;//n ,times
if(n<=1||(n%2==0))
{
cout<<n<<" is not a prime "<<endl;
continue;
}
if(n==2||n==3)
{
cout<<n<<" is a prime "<<endl;
continue;
}
bool flag=false;
L result;
for(int i=0;i!=times;++i)
{
L a=rand()%(n-3)+2;// 2——n-2
power(a,n-1,n,result ,flag);
}
if(flag||result!=1) cout<<n<<" is not a prime"<<endl;
else cout<<n<<" is a prime"<<endl;
}return 0;
}