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?).
Thanks for your timeCode: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



LinkBack URL
About LinkBacks


