/****************************************************************************/
/* Factorizacion de Fermat: Si n es un entero positivo impar, hay           */
/* una correspondencia uno a uno entre las factorizaciones de n como        */
/* producto de dos enteros y las diferencias de dos cuadrados que           */
/* son iguales a n. Buscamos soluciones de n=x^2-y^2=(x-y)(x+y)             */
/* buscando un cuadrado perfecto de la forma x^2-n. Usa LIP.                */
/* El método es muy poco eficiente execepto en el caso de que n sea         */
/* el producto de dos factores de tamaño similar.                           */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.h>

#include "lip.h"

main(int argc, char *argv[])
{
	verylong n=0,t=0,u=0,tmp=0,tmp1=0,fact1=0,fact2=0;

	if (argc!=2) {
		printf("%s <n> intenta factorizar n por el método de Fermat."
			    ,argv[0]);
		return 1;
	}
	zsread(argv[1],&n);                     /* leer n */
	
	zsqrt(n,&t,&tmp);                       /* t parte entera más uno   */
	zsadd(t,1,&tmp);                        /* de la raiz cuadrada de n */
	zcopy(tmp,&t);

	while(1) {
		zsq(t,&u);			                /* u=t^2 */
		zsub(u,n,&tmp);
		zcopy(tmp,&u);                      /* u=t^2 - n */
		if (zsqrt(u,&tmp,&tmp1)==1) break;  /* u es cuadrado perfecto */
		zsadd(t,1,&tmp);                 
		zcopy(tmp,&t);                      /* t=t+1 */
	}
	
	zadd(t,tmp,&fact1);
	zsub(t,tmp,&fact2);
	zwrite(n); printf(" = ");
	zwrite(fact1); printf(" . "); zwriteln(fact2);
		
	return 0;
}