# Miller Rabin Test Implementation doesn't recognize Primes

This is a discussion on Miller Rabin Test Implementation doesn't recognize Primes within the C Programming forums, part of the General Programming Boards category; Hi folks, I'm trying to implement the Miller Rabin Prime Test into C as an exercise and I was hoping ...

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