/*********************************************************
Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
Capitolo 6.5.2 pag. 175 e
Capitolo 9.6.3 pag. 279
*********************************************************/
/*************************************************
 Algoritmo di fattorizzazione di Fermat
 FermatFatt(n,R), dove n e` un intero positivo dispari
 e R e` un parametro fornito dall'utente e indica un 
 intervallo in cui x varia per determinare n=x^2-y^2;
 s R non viene passato, viende definito per default
 R=ceil(n^(1/3)). 
 
 E` efficiente solo se y e`piccolo rispetto a n 
**************************************************/

{ FermatFatt(n,R=-1)=
		local(a,x,y,j);
		if(n<=1|!bittest(n,0),error("Input non valido"));
	 	a=floor(sqrt(n));
	 	if(n==a^2,print(n," e` il quadrato di ",a);return);
		x=a+1;
		y=floor(sqrt(x^2-n));  
        if(n==x^2-y^2,print(n," e` il prodotto di ",x-y," e ",x+y);return);
        if (R==-1, R=ceil(n^(1/3)));
        for (j=1,R,
        			x++;
        			y=floor(sqrt(x^2-n));
        			if(n==x^2-y^2,print(n," e` il prodotto di ",x-y," e ",x+y);return);
        	);
        print (n" non e` del tipo x^2-y^2 per ogni x+j, j nell'insieme {0,... ", R ,"}");
        return; 
}