/*
  Author:  Pate Williams (c) 1997

  Exercise VI.4.1
  "Use Pollard's p - 1 method with k = 840 and a = 2
  to try to factor n = 53467. Then try a = 3."
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 198.
*/

#include <stdio.h>

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

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

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

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

int main(void)
{
  long a = 2, b, d, k = 840, n = 53467;

  d = gcd(b = exp_mod(a, k, n) - 1, n);
  printf("gcd(%ld, %ld) = %ld\n", b, n, d);
  a++;
  d = gcd(b = exp_mod(a, k, n) - 1, n);
  printf("gcd(%ld, %ld) = %ld\n", b, n, d);
  return 0;
}