Miller-Rabin primality Test Error

Hi! I am having problems with this program, for every odd number it returns the number as prime.

here's my program

Code:

/* Miller-Rabin Primality Test *  By- manny721
 *  15 oct 2011
 * */




#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;


int main()
{
   long unsigned int p,q,a=1,f=0,x,i=1,k,u,j;
   bool prime=true;


   cout<<"Enter the lower limit: ";
   cin>>p;
   //cout<<"Enter the upper limit: ";
   //cin>>q;
   cout<<"Enter the security parameter: ";
   cin>>k;


   while(1)
   {
      a = 1;
      
      if(p%2==0)
      {
          cout<<"\n"<<p<<" is composite\n";
          break;
       }  


      while(p-1>=pow(2,f)*a)
      {
          if((p-1)==(pow(2,f)*a))
          {
              while(prime && i<=k)
              {
                  u =  1 + rand() % (p-1);
                  x = fmod(pow(u,a),p);


                  if(x==1 || x==-1)
                  {
                      j = 1;


                      while((x!=-1 || x!=1) && j<=(f-1))
                      {
                          x = fmod(pow(x,2),p);


                          if(x==1)
                          {
                            prime = false;
                            //break;
                          }


                          j = j+1;
                      }


                      if(x==-1)
                      {
                         prime = false;
                         //break;
                      }
                  }


                  i = i+1;
              }
          }
          a = a+2;
      }
           if(prime==true)
           {
               cout<<"\n"<<p<<" is prime\n";
               break;
            }   
           else if(prime==false || (pow(2,f)) > p)           
               {
                   cout<<"\n"<<p<<" is composite\n";
                   break;
               }
      f = f+1;
   }


return 0;
}


]

Is this supposed to be C or C++?

Incidentally, I suggest that you write a function named is_composite that implements Miller-Rabin to determine if its argument is definitely composite, returning a true value if it is. This would then make it easier to concentrate on that part.

I made the changes u suggested but, the program is still returning all odd numbers as prime.

Code:

/* miller-rabin */


#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;


bool is_prime(int p, int k,int a,int f)
{
    int i=1,j,x,u;
    bool prime=true;
    while((prime) && i<=k)
              {
                  u =  1 + rand() % (p-1);
                  x = fmod(pow(u,a),p);


                  if(x==1 || x==-1)
                  {
                      j = 1;


                      while((x!=-1 || x!=1) && j<=(f-1))
                      {
                          x = fmod(pow(x,2),p);


                          if(x==1)
                          {
                            prime = false;
                            //break;
                          }


                          j = j+1;
                      }


                      if(x==-1)
                      {
                         prime = false;
                         //break;
                      }
                  }


                  i++;
              }
    return (prime);          
}
    
int main()
{
    long unsigned int p,q,a=1,f=0,k;
    bool compo=false;


    cout<<"Enter the number: ";
    cin>>p;
    cout<<"Enter the security parameter: ";
    cin>>k;
    
    while(1)
    {
        a = 1;
        
        while(p-1>=pow(2,f)*a)// to determine the values of f and a 
        {
            if((p-1)==(pow(2,f)*a))
              {
                  compo = is_prime(p,k,a,f);
              }
             
            a=a+2;  
        }
        
        if(compo==true || (pow(2,f)) > p)
           {
               cout<<"\n"<<p<<" is composite\n";
               break;
            }   
        else if(compo==false)           
               {
                   cout<<"\n"<<p<<" is prime\n";
                   break;
               }
        f++;
    }
    return 0;
}

Since you persist in using C++ constructs, I am assuming this is C++ and hence I am moving this thread accordingly.

Originally Posted by manny721

I made the changes u suggested but, the program is still returning all odd numbers as prime.

Miller-Rabin does not determine primality; it determines if the number tested is composite, otherwise with sufficient number of iterations, the number tested is probably prime. You should already know this since I can see it in your basic loop structure. This is why I suggested that the function be named is_composite. It should also only hava a single parameter, i.e., the number to test.

Did you write say, the pseudocode before you started implementing, or otherwise followed some already available pseudocode? If so, post the pseudocode. Another thing to do is to comment the various parts of your implementation with an outline of this algorithm.

(Basically, I could go through your code to figure out if it does what Miller-Rabin is supposed to do using say, the Wikipedia article as a reference, but that should be your job, not mine.)

Also: you should give your variables descriptive names, and although you did indent your code, the consistency of your indentation can be improved.

Sorry, for begin so ambigious and tanks for the advice.
I got the pseudocode from my textbook. It is as follows:-

1) Find an odd integer 's' such that p-1=(2^r) *s.

2) Select at random a nonzero integer 'a' in range (1,p-1] for k times, where k is the security parameter.

3) compute
b = a^s (mod p)

4) if(b==-1 || b==1) go to step 5.

5) for i=1,......,r-1 , calculate
c = b^2 (mod p)
if (c==1)
prime = false
after the loop
if(c==-1)
prime=false
6) return prime

At a glance, this wont do what you must want:

Code:

while((x!=-1 || x!=1) && j<=(f-1))

Every possible value of x is either not equal to -1 or not equal to 1.
This makes it effectively:

Code:

while(true && j<=(f-1))

However you must have screwed up your logic somewhere because if you just make it an and, then it wont go into that loop because the if-statement before it ensures that it would not.
Verify your code against the algorithm again.

Originally Posted by laserlight

Miller-Rabin does not determine primality; it determines if the number tested is composite, otherwise with sufficient number of iterations, the number tested is probably prime.

After about ((log(n)*log(log(n))/2) sequential iterations Miller-Rabin is fully deterministic. Anecdotal (observational) evidence supports an even lower (much much) lower bound, it's just never been proven. Something like log2(log2(n)) might be sufficient, probably?

I changed the code a bit and it works for integers below 100 but for every odd number above 100 it returns the number as prime. I'll post the code below :-

Code:

#include<iostream>#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
using namespace std;


bool is_composite(long unsigned int num,long unsigned int k,long unsigned int exp,long unsigned int odd_num)
{
  int x,u,i=1,j,temp;


  for (int i = 1; i <= k;i++)
        {
            u = 1 + (rand() % (num-1));
            temp = odd_num;
            x = fmod(pow(u,temp),num);


            while(temp!=num-1 && x!=1 && x!=num-1)
            {
		       x=(x*x)%num;
		       temp=temp*2;
            }


            if(x!=num-1 && temp%2==0)
            {
		       return false;
            }
        }
	return true;
}


int main()
{
    long unsigned int num,k,exp,odd_num,flag=0;
    bool compo;


    cout<<"Enter the number: ";
    cin>>num;
    cout<<"Enter the security parameter: ";
    cin>>k;


    if (num < 2 || num % 2 == 0)
       {
        cout<<"\n"<<num<<" is composite\n";
        flag=1;
       }


    odd_num = num - 1;
    exp = 0;
    while (odd_num % 2 == 0)
    {
        odd_num /= 2;
        exp++;
    }
    if(num-1 == pow(2,exp)*odd_num)
       compo = is_composite(num,k,exp,odd_num);
    else if(flag!=1)
       cout<<"\n"<<num<<" is composite\n";


     if(compo==true && flag!=1)
       cout<<"\n"<<num<<" is prime\n";
     else if(flag!=1)
       cout<<"\n"<<num<<" is composite\n";


    getch();
    return 0;
}

Thank you! for your help