/*
  Author:  Pate Williams (c) 1997

  Exercise V.2.1
  "x ^ 2 - 1, x_0 = 2, n = 91." -Neal Koblitz-
  See "A Course in Number Theory and "Cryptography"
  by Neal Koblitz second edition page 142.
*/

#include <math.h>
#include <stdio.h>

long gcd(long a, long b)
{
  long r;

  while (b > 0)
    r = a % b, a = b, b = r;
  return a;
}

int main(void)
{
  long d, delta, k = 0, l = 0, n = 91, x0 = 2, xj = x0, xk;

  for (;;) {
    k = k + 1;
    xk = (xj * xj - 1) % n;
    if (k == pow(2, l)) {
      x0 = xj;
      l++;
    }
    delta = xk - x0;
    if (delta < 0) delta += n;
    d = gcd(delta, n);
    printf("gcd(%2ld - %2ld, %2ld) = %ld\n", xk, x0, n, d);
    if (d != 1 && d != n) break;
    xj = xk;
  }
  printf("n = %ld = %ld * %ld\n", n, d, n / d);
  return 0;
}