/*
Magma implementation of AKS primality proof algorithm, by Allan K. Steel
(note my initials -- nice coincidence :-)), 
<[Allan's first name]@maths.usyd.edu.[Australia]>, 8/8/02.

The power test is done at the beginning in polynomial time (with a log factor).
Note that I use NextPrime to loop through the values of r.  This is faster than
testing whether each new r is prime: NextPrime(r) computes with proof the first
prime greater than r (and in deterministic polynomial time for r < 3.4*10^14).
This is ironic of course, in that we have can prove any number < 3.4*10^14
prime in deterministic polynomial time (and in < 0.001 secs in practice),
which is way above the reasonable testing range for the AKS algorithm.
*/

function AKS(n)
    if IsPower(n) or n gt 2 and IsEven(n) then
        return false;
    end if;

    logn := Log(2, n);
    r := 3;
    while r lt n do
        if GCD(n, r) ne 1 then
            return false;
        end if;

        q := D[#D] where D := PrimeDivisors(r - 1);
        if q ge 4*Sqrt(r)*logn and Modexp(n, (r - 1) div q, r) ne 1 then
            break;
        end if;

        r := NextPrime(r);
    end while;
    

    P<x> := PolynomialRing(IntegerRing(n));
    for a := 1 to Floor(2*Sqrt(r)*logn) do
        if Modexp(x - a, n, x^r - 1) ne x^(n mod r) - a then
            return false;
        end if;
    end for;

    return true;
end function;