/*
  Author:  Pate Williams (c) 1997

  Exercise IV.2.4
  "Show why the 35-bit number 23360947609 is a
  particularly bad choice for n = pq, because
  the two prime factors are too close to one
  another; that is, show that n can be easily
  factored by "Fermat factorization."
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 96.
*/

#include <stdio.h>
#include <string.h>
#include "lip.h"

void strtoz(char *s, verylong *zn)
{
  long i;
  verylong za = 0;

  zzero(zn);
  zintoz(s[0] - '0', zn);
  for (i = 1; i < strlen(s); i++) {
    zsmul(*zn, 10, &za);
    zsadd(za, s[i] - '0', zn);
  }
  zfree(&za);
}

int main(void)
{
  char s[16] = "23360947609";
  verylong za = 0, zb = 0, zd = 0, zn = 0, zp = 0;
  verylong zq = 0, zs = 0, zt = 0;

  strtoz(s, &zn);
  zsqrt(zn, &za, &zd);
  zsadd(za, 1, &zt);
  for (;;) {
    zsq(zt, &za);
    zsub(za, zn, &zb);
    zsqrt(zb, &zs, &zd);
    if (zscompare(zd, 0) == 0) break;
    zsadd(zt, 1, &za);
    zcopy(za, &zt);
  }
  zadd(zt, zs, &zp);
  zsub(zt, zs, &zq);
  printf("n = ");
  zwrite(zn);
  printf(" = ");
  zwrite(zp);
  printf(" * ");
  zwriteln(zq);
  zfree(&za);
  zfree(&zb);
  zfree(&zd);
  zfree(&zn);
  zfree(&zp);
  zfree(&zq);
  zfree(&zs);
  zfree(&zt);
  return 0;
}