\\Agrawal-Kayal-Saxena primality-proving algorithm assuming
\\enough Sophie Germain primes. May need increased precision
\\to deal with very big numbers. Slow for large primes.
\\by Felipe Voloch
\\Usage: aks(n) is you want a 0/1 answer or aks(n,1) if
\\you want a verbose answer.
\\ 9/13/02 Some improvements and corrections
\\ 10/2/07 Commented out ispower since now gp has a built-in version
\\{
\\default(realprecision,100)
\\}
\\{
\\ispower(n,r)=r=0;for(b=2,floor(log(n)),if(round(n^(1/b))^b==n,r=1;break));r
\\}

{
aks(n,ver,r,s)=s=1;if(n==1,s=0;if(ver,print(n" is a unit")),
if(n==2 || n==3,if(ver,print(n" is prime")),
if(n%2==0 || n%3 ==0,s=0;if(ver,print(n" is composite")),
if(ispower(n),s=0;if(ver,print(n" is a perfect power")),
r=5;while(r<n,
if(gcd(n,r)!=1,s=0;if(ver,print(n" is composite"));break);
if(r>0.062*log(n)^2 &&aks(r,0)&&aks((r-1)/2,0)&&n^2%r!=1,break);r++);
if(s==1 && r < sqrt(n),if(ver,print("entered loop with r="r));
for(a=1,floor(0.043*log(n)^2+10),
if(Mod(Mod(1,n)*(x-a),Mod(1,n)*(x^r-1))^n!=
Mod(Mod(1,n)*x,Mod(1,n)*(x^r-1))^n-Mod(Mod(a,n),Mod(1,n)*(x^r-1)),
s=0;if(ver,print(n" is composite and "a" is a witness"));break)));
if(s==1,if(ver,print(n" is prime")))))));s
}