/*********************************************************
Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
Capitolo 6.4. pag. 166 e
Capitolo 9.6.3 pag. 276
*********************************************************/
/*************************************************
 Algoritmo di fattorizzazione di Fermat-Lehman
 FermatLehmanFatt(n), dove n e` un intero positivo 
 dispari. Per prima cosa si esegue una divisione per tentativi
 fino al livello  R=ceil(n^(1/3)). 
 Dopodich\`e si cerca una fattorizzazione di n
 della forma 4kn=x^2-y^2, dove k varia tra 1 e R.  
**************************************************/

{ FermatLehmanFatt(n)=
		local(a,b,t,s,m,R,R1,k);
		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);
	 	R=ceil(n^(1/3)); 
	 	R1=n^(1/6); 
	 	/******* trial division sui dispari fino al livello R *******/
	 	forstep (m=3,R,2,if (n%m==0, print(m," divide ",n);return));
	 	/****** Ciclo di Fermat  *******/
	 	for (k=1,R,t=2*sqrt(k*n);
	 		for(a=ceil(t), floor(t+R1/(4*sqrt(k))),
	 				s=a^2-4*k*n;b=floor(sqrt(s));
	 		   		if(b^2==s,print(gcd(a+b,n)," divide ",n);
	 		   			print(gcd(a-b,n)," divide ",n);
	 		   			return
	 		   		   );
	 		   	);
	 		 );
        print(n," e` primo");
        return; 
}