Thread: Miller-Rabin primality Test Error

  1. #1
    Registered User manny721's Avatar
    Join Date
    Oct 2011
    Posts
    4

    Red face 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;
    }
    
    
    ]

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User manny721's Avatar
    Join Date
    Oct 2011
    Posts
    4
    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;
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Since you persist in using C++ constructs, I am assuming this is C++ and hence I am moving this thread accordingly.

    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User manny721's Avatar
    Join Date
    Oct 2011
    Posts
    4
    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

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 10-16-2011 at 12:24 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User gardhr's Avatar
    Join Date
    Apr 2011
    Posts
    151
    Quote Originally Posted by laserlight View Post
    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?
    Last edited by gardhr; 10-16-2011 at 01:05 PM. Reason: reword for clarity

  8. #8
    Registered User manny721's Avatar
    Join Date
    Oct 2011
    Posts
    4

    Smile

    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Rabin-Karp algorithm
    By Aisthesis in forum C++ Programming
    Replies: 23
    Last Post: 09-28-2010, 07:57 AM
  2. Replies: 1
    Last Post: 08-06-2010, 01:50 PM
  3. Primality Tester
    By eurylochus1 in forum C Programming
    Replies: 13
    Last Post: 09-27-2008, 10:08 AM
  4. An Interview with Bjarne Stroustrup By Michael Miller
    By kermi3 in forum Article Discussions
    Replies: 9
    Last Post: 03-15-2005, 10:59 AM
  5. Test script error
    By Aalmaron in forum C++ Programming
    Replies: 7
    Last Post: 01-08-2004, 01:47 PM