Thread: Miller Rabin Test Implementation doesn't recognize Primes

  1. #1
    Registered User
    Join Date
    Aug 2010
    Posts
    1

    Post Miller Rabin Test Implementation doesn't recognize Primes

    Hi folks, I'm trying to implement the Miller Rabin Prime Test into C as an exercise and I was hoping you could give me a few pointers where to look for my mistake. The following Code should work if i understood the Algorithm correctly, but it sometimes(pretty often really) tags primes as nonprimes(or did the rules change and 17 isn't a prime anymore?).

    Code:
    	long int a,a2,r2,n,d,x,k,j,r; //define variables	
    	char input[17];			
    	fgets(input,17,stdin);
    	n = strtol (input,NULL, 10);		//input number, make int from input
    	
    	k = x = n-1;						//split even and odd factors by:
    	while (r == 0 ){x = x/2; r = x%2;;}	//find d by dividing through 2
    	d = x;
    	j = log (k/d) / log(2.0);			//find exponent j from n-1= d* 2^j through log2 n-1/d = log2 of the even factor
    	printf("%ld -1 = %ld * 2^%ld",n,d,j);//show the odd and even factors
    	/* initialize random generator */
    	srand ( time(NULL) );
    	printf("\n");
    	a = rand();	a = a % n;				//make random integer form double rand(), make a €[0,n-1]
    	r = rand();	r = r % j;				//make random integer form double rand(), make r €[0,j-1
    	a2 = pow(a,d);a = a2 % n;			// a^d mod n
    	r2 = pow(a,(d * pow(2,r)));r = r2 % n;//a^d*2^r mod n
    	if (a == 1) {printf("Ist prim");} // is prime
    	else if (r*r == 1) {printf("Ist prim");} //is prime
    	else {printf ("Ist nicht prim");} //isnt prime
    Thanks for your time

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Your code doesn't actually look like this algorithm

    Miller–Rabin primality test - Wikipedia, the free encyclopedia
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Integer Emulation
    By Elysia in forum C++ Programming
    Replies: 31
    Last Post: 03-18-2008, 01:03 PM
  2. check value
    By Ideswa in forum C++ Programming
    Replies: 15
    Last Post: 03-18-2006, 01:55 PM
  3. C++ Operator Overloading help
    By Bartosz in forum C++ Programming
    Replies: 2
    Last Post: 08-17-2005, 12:55 PM
  4. MSVC Template Constructor/Assignment Errors
    By LuckY in forum Windows Programming
    Replies: 3
    Last Post: 07-22-2005, 02:57 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM