/*
  Author:  Pate Williams (c) 1997

  Exercise V.3.1
  "Use Fermat factorization to factor: (a) 8633,
  (b) 809009, (c) 92296873, (d) 88169891, (e) 4601."
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 153.
*/

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

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

  *t = sqrt(n) + 1;
  for (;;) {
    s = *t * *t - n;
    r = sqrt(s);
    if (s - r * r == 0) break;
    *t = *t + 1;
  }
  *a = *t + r;
  *b = *t - r;
}

int main(void)
{
  long a, b, i, t;
  long n[5] = {8633, 809009l, 92296873l, 88169891l, 4601};

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