Miller Rabin Deterministic Algorithm

general
,
1

I wrote the following code for finding prime numbers between two given integers n,m

Instead of the standard sieve method I tried using the Miller-Rabin test.

http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

But the following code is giving a wrong answer in prime1, please help.

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<numeric>
#include<stack>
#include<set>
#include<map>

using namespace std;

#define inf 1000000007
#define mp make_pair
#define pb push_back
#define f(i,j) for(int i=0;i<j;i++)
#define fe(i,j) for(int i=0;i<=j;i++)
#define fr(i,j) for(int i=j;i>0;i--)
#define fre(i,j) for(int i=j;i>=0;i--)

//2 7 61

map<long long int,long long int> prm;
long long int t[3]={2,7,61};

long long int mod_pow(long long int a,long long int b,long long int n){
  long long int res=1;
  while(b){
    if(b%2){
      res=(res*a)%n;
    }
    a=(a*a)%n;
    b/=2;
  }
  return res;
}

pair<long long int,long long int> thed(long long int n){
  long long int cnt=0;
  while(n%2==0){
    n/=2;
    cnt++;
  }
  return mp(n,cnt);
}

int isprime(long long int n){
  if(n==1){
    return 0;
  }
  else if(n==2){
    return 1;
  }
  else if(n==3){
    return 1;
  }
  else if(n==5){
    return 1;
  }
  else if(n==7){
    return 1;
  }
  else if(n==61){
    return 1;
  }
  else{
    long long int a,x,d,flag;
    int s;
    pair<long long int,long long int> ast=thed(n-1);
    d=ast.first;
    s=ast.second;
    f(i,3){a=t[i];
      x=mod_pow(a,d,n);
      if(x==1 or x==n-1){
	    continue;
      }
      else{
	    flag=1;
  	    f(i,s-1){
	      x=(x*x)%n;
	      if(x==1){
	        return 0;
	      }
	      if(x==n-1){
	        flag=0;
	        break;
	      }
	    }
	    if(flag){
	      return 0;
	    }
      }
    }
    return 1;
  }
}

int main(){
  int t;
  long long int n,m;
  cin>>t;
  while(t--){
    cin>>m>>n;
    for(long long int i=m;i<=n;i++){
      if(isprime(i)){
	cout<<i<<endl;
      }
    }
    cout<<endl;
  }
}
2

Because it may be missing some prime numbers or test non-prime numbers as prime.
You can check by producing primes by both sieve and millerrabin and compare the result.

3

I used the deterministic version of the test where we have to check only some testers for n<=1,000,000,000 having a=2,7,61, as stated in Wikipedia,

4

How can it be missing some numbers if it is deterministic?
I checked with codes of other users and using the diff command and it seems to give the correct answer.

5

@epsilon_0
you can understand and try this
The Algorithm is slower than Fermat’s Little primality test but is still preferred due to it’s high accuracy.
Try out this problem on SPOJ/PON

Here’s  the python implementation –
import random

def exp(a,p,m):
	if (p==0):
		return 1
	elif (p%2==1):
		return (a*exp(a,p-1,m))%m
	x=exp(a,p/2,m)
	return (x*x)%m

def miller_rabin(p):

	if (p==2 or p==3):return 1
	if (p%2==0):return 0
	if (p<3):return 0

	for i in range(10):
		#random 'a'
		a = random.randrange(2,p-2)

		s=p-1
		while(s%2==0):s/=2

		mod = exp(a,s,p)
		if (mod==1 or mod==p-1):
			continue
		
		flag=0
		while(s!=(p-1)):
			mod = exp(a,s,p)
			if (mod==(p-1)):
				flag=1
				break
			s*=2
		if (flag==0):
			return 0
	return 1