1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

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