/*********************************************************
Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
Capitolo 6.4. pag. 166 e
Capitolo 9.6.3 pag. 276
*********************************************************/
{aks(n)= local(b,r,logn,log2n,l,m,k,phir);

/***************** Controlli iniziali *******************/ 
if((n <= 3)&(n>1), print(n, " e` primo"); return(1)); 
if( n<=1, error("Input non valido"));
if(!bittest(n,0), print(n, " e` pari"); return(0));
logn=log(n);

/********** Test per le potenze di primi dispari ********/ 

if(issquare(n), print(n," e` il quadrato di ",floor(sqrt(n))); 
			return(0));
l= ceil(exp(logn/ 3)); 
forprime(p=3,l,  
     m = ceil(logn/log(p)); 	
     forstep(k=3, m,2,  
           	if(n==p^k, print(n," e` uguale a ",p, " elevato a ",k);
           		return(0))));
print(n," non e` una potenza prima"); 

/** Ricerca del minimo r per cui n e` generatore di Zr **/ 

log2n = logn/log(2);
r = nextprime(4*log2n^2);
print("r ", r);
until(isprimitiveroot(n,r),r = nextprime(r+2);print("r ", r);
   	if( gcd(n,r) > 1 &&  gcd(n,r) < n, 
   			print(n," e` diviso da ",gcd(n,r));
     	    return(0) ));
phir=eulerphi(r);
s=floor(2*sqrt(phir)*log2n);

/************* Test polinomiale di AKS  ***************/ 
   
print("aks");
for( b=1, s,
     if( gcd(b,n) > 1 &&  gcd(b,n) < n, 
        	print(n," e` diviso da ",gcd(b,n)); return(0) );
     if( Mod(x + Mod(b,n),x^r-1)^n != Mod(x^n + Mod(b,n),x^r-1),
            print(n," e` composto"); return(0))
   );
print(n," e` primo");
return(1);
}