Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Miller-Rabin primality Test Error (http://www.go4expert.com/forums/miller-rabin-primality-test-error-t26942/)

manny721 16Oct2011 18:47

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 */

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

bool is_prime(int num, int k,int odd_num,int exp)
{
        int i=1,j,x,u;
        bool prime=true;
    while(prime && i<=k)
              {
                  u =  1 + rand() % num; // generating a random number in the range (1,num-1]
                  x = fmod(pow(u,odd_num),num);

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

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

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

                          j++;
                      }

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

                  i++;
              }
    return (prime);         
}
       
int main()
{
        long unsigned int num,odd_num=1,exp=0,k;
    bool compo=false;

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

thanks in advance


All times are GMT +5.5. The time now is 03:18.