9 replies to this topic

[manny721]

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

here's my program

/* 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 for your help

[WingedPanther]

Have you checked any of your intermediate results for accuracy? What odd numbers are you using?

[manny721]

WingedPanther said:

What odd numbers are you using?

For both composite odd numbers (like 9,15,21,etc.) and prime numbers (like 13,17,etc.).

[WingedPanther]

I just copied your code. It doesn't even compile. How on earth are you running it?

[manny721]

WingedPanther said:

I just copied your code. It doesn't even compile. How on earth are you running it?

if you are using Linux compile it using g++ instead of gcc to compile.
If you are using windows use either code blocks IDE or dev c++.

---------- Post added at 12:28 PM ---------- Previous post was at 12:15 PM ----------

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, compile it using g++ in Linux or code blocks IDE in Windows.

#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.

[WingedPanther]

I was using g++, but getting f not defined in the code you originally posted.

[manny721]

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

Change the above code in function is_prime to

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

It should compile then, anyway did you try the code that I posted earlier today. I am having some problems as I mentioned earlier, I would really appreciate your help.

[WingedPanther]

I entered 111 and 5, and got composite. Can you give more details about the inputs you are giving?

[manny721]

WingedPanther said:

I entered 111 and 5, and got composite. Can you give more details about the inputs you are giving?

Are you using the second program I posted? That program returns 5 as prime and 111 as composite. Sorry, I made a mistake

Quote

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

This program returns every odd number above 100 as composite.

Try the values of primes from the List of Primes available in Wikipedia(List of prime numbers - Wikipedia, the free encyclopedia).

I have checked and it works for integers below 100.

[WingedPanther]

I was using the second code.