# Miller Rabin Test Implementation doesn't recognize Primes

Printable View

• 08-06-2010
bavcn
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
• 08-06-2010
Salem
Your code doesn't actually look like this algorithm

Millerâ€“Rabin primality test - Wikipedia, the free encyclopedia