aks algorithm and polynomial

[jocelynl]

I was looking at the AKS alogorithm
and notice that i'm not familiar with polynomial modulus
Here is the algorithm.
I need some help with

if ( (x-a)^n is not (x^n-a) (mod x^r-1,n) ) then output COMPOSITE

I don't see what the ,n does?

Input: Integer n > 1

if (n has the form ab with b > 1) then output COMPOSITE

r := 2
while (r < n) {
	if (gcd(n,r) is not 1) then output COMPOSITE
	if (r is prime greater than 2) then {
 		let q be the largest factor of r-1
		if (q > 4sqrt(r)log n) and (n^((r-1)/q) is not 1 (mod r)) then break
	}
	r := r+1
}

for a = 1 to 2sqrt(r)log n {
	if ( (x-a)^n is not (x^n-a) (mod x^r-1,n) ) then output COMPOSITE
}

output PRIME;

Joss

[Maybeso]

Joss,

I'm not that familiar with it either, but I tried interpreting it in different ways, then coding a crude program to test it.

if ( (x-a)^n is not (x^n-a) (mod x^r-1,n) ) then output COMPOSITE

The only interpretation which produced the correct results was:
Raise (x - a) to the nth power,
(mod x^r-1) means (mod r) on the powers of x, which results in adding the x^(r+i) term to the x^i term.
Do the (mod n) on the individual coefficients.

The foundation of the method is that if you raise (x - a) to a prime n, all the coefficients will be either 1 or divisible by n.
(The nth row of pascals triangle contains only multiples of n for prime n.) When you do (mod n), you get 1, 0, 0, ..., 0, a
-- which is (x^n-a).

The problem is you're working with n terms, which is too slow for large n. The genius of AKS is, for certain values of r, if you restrict yourself to r terms -- wrapping the rest around -- the coefficients will still be divisible by n for prime n, and divisible by some factor of composite n. That is what all their high math language was proving.

Hope this helps,

Maybeso