AKS prmality test

[killo]

Wow thanks for explaining that to me I'll carefully look at this over the next few days and tell you how I get on.
Some preliminary questions:

Where you said:

and you had previously found r=7, you can subtract off
(x^7-1)*3x^2 = 3x^9-3x^2

where did you get the 3x^2 from? did you just choose that to get the polynomial up to the 9th order? How did you go about choosing it?

So now, my general understanding is that you need to keep on subtracting off (x^r-1) from both sides of the equation until they are as small as you can get them, and then once that's done, take both sides mod n and then compare the two sides to see if they're equal?

(Also I have no Idea what a quotient ring is, but it doesn't seem like I need to understand that)