Miller-Rabin(素数テスト)

3770 ワード

フェルマの小さい定理と二次探知の定理を用いて素数のテストを行う
#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;
}