/*
  Author:  Pate Williams (c) 1997

  Exercise V.3.4
  "Use the generalized Fermat factorization to
  factor: (a) 68987, (b) 29895581,
  (c) 19578079, (d) 17018759." -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 153.
*/

#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;
}

void factor(long n, long *k, long *t, long *a, long *b)
{
  long c, i, r, s;

  *k = 3;
  for (;;) {
    c = sqrt(*k * n);
    for (i = 1; i < 5; i++) {
      *t = c + i;
      s = *t * *t - *k * n;
      r = sqrt(s);
      if (s - r * r == 0) {
        *a = gcd(*t + r, n);
        *b = n / *a;
        if (*a > *b)
          r = *a, *a = *b, *b = r;
        return;
      }
    }
    *k = *k + 2;
  }
}

int main(void)
{
  long a, b, i, k, t;
  long n[4] = {68987l, 29895581l, 19578079l, 17018759l};

  for (i = 0; i < 4; i++) {
    factor(n[i], &k, &t, &a, &b);
    printf("k = %ld t = %8ld n = %8ld = %ld * %ld\n", k, t, n[i], a, b);
  }
  return 0;
}