AKS - A polynomial-time algorithm for testing primality.

[Maybeso]

Sorry about that;
After reading that paragraph again, I realise that I was thinking about aspects of sieving and trial factoring, but trying to apply them to primality testing.

I should have limited myself to --
Use AKS when you have an actual number to test for primality that wasn't generated by plugging values into a formula, or was given to you with no formula + parameters to regenerate it. If you have the formula, its form and the relative scale of the parameters should be enough to select (or write) a primality-testing program that will out-perform AKS.

I also noticed I forgot to mention a few things:

Yes, AKS is a test-until-you-fail method.
- You evaluate the equation for a given a, then check for non-zero terms.
- If you find one, then n is composite and you can stop.
- Otherwise you try again with the next value of a.
- If you check the entire range of values, then n is prime.

The math behind evaluating f(x) (mod (x^r - 1).

Consider x^7 mod (x^7 - 1), If we plug in any value, we get
(N + 1) mod N == 1 mod N

Now Consider
Ax^11 + Bx^10 + Cx^9 + Dx^8 + Ex^7 + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1)
= (Ax^4 + Bx^3 + Cx^2 + Dx + E)x^7 + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1)

But x^7 = 1 mod (x^7 - 1), so
= (Ax^4 + Bx^3 + Cx^2 + Dx + E)(1) + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1)
= Fx^6 + Gx^5 + (A+H)x^4 + (B+I)x^3 + (C+J)x^2 + (D+K)x + (E+L) mod (x^7 - 1)

And this gives us the wrap-around behavior described before.

Finally, after processing the convolution matrix, to subtract (x^n - a), simply subtract -a from the first term and 1 from the (n mod r) term.

Regards,

Bruce