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