gistfile1.h

#include <stdio.h>
#include <stdlib.h>

int
expmod(int a, int m, int n)
{ // (a ** m) % n
  int temp = 1;
  while (m != 0) {
    temp *= a;
    temp %= n;
    m--;
  }
  return temp;
}

int
main(int argc, char **argv)
{
  int a, b, ki;
  int m = 0;
  int k = 0;

  if (argc < 2) {
    printf("Usage: ./mr <n>");
    exit(1);
  }
  
  int n = atoi(argv[1]);
  
  int false_witnesses = 0;
  
  while ((m % 2) == 0) {
    k += 1;
    m = (n - 1) / (1 << k); // (n - 1) / (2 ** k)
  }

  printf("k = %d; m = %d\n", k, m);
  
  for (a = 2; a < n; a++) {
    b = expmod(a, m, n);

    if (b == 1) {
      printf("%d, ", a);
      false_witnesses++; 
    } else {
      for (ki = 0; ki < k; ki++) {
//        if (b == -1 % n) {
        if (b == n - 1) {
          printf("%d, ", a);
          false_witnesses++;
          break;
        } else {
          b = (b * b) % n;
        }
      }
    }
  }

  printf("\nWitnesses: %d\n", n - 1);
  printf("False Witnesses: %d\n", false_witnesses);

  printf("Percentage: %f%%\n", 100*((float)false_witnesses / (n - 1)));
  
}