Name: Anonymous 2015-05-06 19:42
Meh
// Find a witness for the Rabin-Miller test
// http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
// (variable names following article)
#include <stdio.h>
#include <math.h>
int gcd(int a, int b) {
int c;
while(a != 0) {
c = a;
a = b%a;
b = c;
}
return b;
}
int maxpowerof2(int n) {
int r = 0;
while(n % 2 == 0) {
n /= 2;
r++;
}
return r;
}
int main(void) {
int r, n, a, i, s, d;
printf("Give n: ");
fflush(stdout);
scanf("%d", &n);
s = maxpowerof2(n - 1);
d = (n - 1)/pow(2, s);
printf("n - 1 = 2^s * d\n"
"%d = 2^(%d) * %d\n", n - 1, s, d);
for(a = 1; a < n; a++) {
if(gcd(a, n) == 1) {
if((int)pow(a, d) % n != 1) {
for(r = 0; r < s; r++)
if((int)pow(a, pow(2, r)*d) % n == n - 1) break;
if(r == s) {
printf("Found a witness: %d\n", a);
break;
}
}
}
}
return 0;
}