/*
  Author:  Pate Williams (c) 1997

  Exercise II.1.1
  "For p = 2, 3, 5, 7, 11, 13, 17, find the
  smallest integer which determines F_p*
  and determine how many of the integers
  1, 2, 3, ..., p - 1 are generators.
*/

#include <stdio.h>

long exp_mod(long x, long b, long n)
/* returns x ^ b mod n */
{
  long a = 1l, s = x;

  while (b != 0) {
    if (b & 1l) a = (a * s) % n;
    b >>= 1;
    if (b != 0) s = (s * s) % n;
  }
  return a;
}

int main(void)
{
  int found, printed;
  long p[7] = {2, 3, 5, 7, 11, 13, 17};
  long count, i, j, k, l, pi, q[18], t;

  q[0] = 0;
  for (i = 0; i < 7; i++) {
    count = 0;
    printed = 0;
    pi = p[i];
    printf("F_%2ld ", pi);
    for (j = 1; j < pi; j++) {
      /* compute all powers of j */
      for (k = 1; k < pi; k++)
        q[k] = exp_mod(j, k, pi);
      /* sort the powers of j */
      for (k = 0; k < pi - 1; k++)
        for (l = k + 1; l < pi; l++)
          if (q[k] > q[l])
            t = q[k], q[k] = q[l], q[l] = t;
      found = 1;
      for (k = 1; found && k < pi; k++)
        found = k == q[k];
      if (found) {
        if (!printed) {
          printed = 1;
          printf("generator = %2ld ", j);
        }
        count++;
      }
    }
    printf("# generators = %ld\n", count);
  }
  return 0;
}