\\ -----------------------------------------------------------------------------
\\            PRIMALITY TEST BY M. AGRAWAL, N. KAYAL AND N. SAXENA
\\ -----------------------------------------------------------------------------
\\      Implementation using PARI-GP, 16/08/2002, 16:49, Folkmar Bornemann
\\ -----------------------------------------------------------------------------
\\ NOTE: n should be greater than 1000 for the simple device in Step #2
\\ -----------------------------------------------------------------------------
\\ n = nextprime(2^27);  run-time 9min 21s on a 1.7GHz PC
\\ n = 628363443011;     run-time 1h 54min 25s on a 1.7GHz PC
\\ -----------------------------------------------------------------------------
\\ !!!! Speed-Ups by a factor of 300 and more are possible to some ideas of !!!!
\\ !!!!    Hendrik W. Lenstra Jr. and José Felipe Voloch. Have a look at    !!!!
\\ !!!!         http://www.ma.tum.de/m3/ftp/Bornemann/PARI/aks2.txt         !!!!
\\ -----------------------------------------------------------------------------

AKS(n) =
{
    local(t,r,q,s,X,a,k,d,p,out);

\\ Input
\\      n : the natural number to be tested
\\ Output
\\      0 : n is composite
\\      1 : n is prime
\\     -1 : n is too small for the simple device in Step #2

    if( n <= 1000, return (isprime(n)) ); \\ make sure that n is not too small

\\ -----------------------------------------------------------------------------
\\ Step #1: testing for prime-power using 2-adic Newton as provided by PARI's
\\          "polrootspadic" command
\\ -----------------------------------------------------------------------------

    if( issquare(n),
        return(0),
\\  else
        m = floor(log(n)/log(3));
        forprime( k=3, m,
            d = ceil(log(n)/log(2)/k)+1;
            p = component(lift(
                Mod(polrootspadic(x^k-n,2,d+1),2^(d+1))),1);
            if( n==p^k, return(0) );
        );
    );

\\ -----------------------------------------------------------------------------
\\ Step #2: Looking for admissible (q,r,s) as in Theorem 1 of Daniel Bernstein:
\\          An Exposition of the Argrawal-Kayal-Saxena Primality-Proving
\\          Theorem, http://cr.yp.to/papers/aks.ps
\\          The admissible triple is chosen in a way as to optimize run-time for
\\          Step#3 in a simplified asymptotic model using Sophie-Germain-primes.
\\ -----------------------------------------------------------------------------
\\ t = 17.4929;     \\ asymptotic optimal for FFT-multiplication
\\ t = 61.5789;     \\ asymptotic optimal for Karatsuba-multiplication
\\ t = 144.8858;    \\ asymptotic optimal for normal multiplication
\\ ... PARI seems to use Karatsuba-multiplication for polynomials
\\ -----------------------------------------------------------------------------

    t = 61.5789;
    r = nextprime(((4/((t+1)*log(t+1)-t*log(t)))^2*log(n)^2));
    until(isprime((r-1)/2) && (Mod(n,r)^2 != 1),r = nextprime(r+2)); print(r);
    q = (r-1)/2;
    s = ceil(solve(x=1,floor(t*q),
         (lngamma(q+x)-lngamma(q)-lngamma(x+1))/log(n)/2/floor(sqrt(r))-1));
    print(s);
    if( gcd(r,n) != 1, return(0) );
    if( s>n, return(-1) );

\\ -----------------------------------------------------------------------------
\\ Step #3: AKS type of for-loop
\\ -----------------------------------------------------------------------------

    X = Mod(Mod(1,n)*x,x^r-1);
    for( a=1, s-1,
        if( gcd(a,n) != 1,     return(0) );
        if( (X-a)^n  != X^n-a, return(0) );
    );
    return(1);
}