/*********************************************************
Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
Test per individuare una potenza prima. Utilizzato in aks.gp
*********************************************************/

{primepower(n)=
    local(a,r,q,logn,l,m,k);
   if((n <= 3)&(n>1), print(n, " e` primo"); return);
   \\if(n<=1|!bittest(n,0),error("Input non valido"));
   logn=log(n);
   
    if(issquare(n), print(n," e` il quadrato di ",floor(sqrt(n))); return(0));
     l= ceil(exp(logn/ 3));	 
     forprime(p=2,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(1))));
     print(n," non e` una potenza prima");
     return(0) ;
}