Miller-Rabin primality Test Error

Discussion in 'C++' started by manny721, Oct 16, 2011.

  1. manny721

    manny721 New Member

    Joined:
    Oct 16, 2011
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    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
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice