On the AKS test

[fetofs]

Hi guys! I've been trying to implement various algorithms from number theory. In the AKS test, there is one step where it asks for the calculation of



Does this mean I have to reduce modulo X^r-1 first, then mod n? If so, what is a good algorithm to reduce a polynomial modulo something (assume I already have addition, subtraction, multiplication, division, exponentiation)? I mean, I could do , but that seems too redundant.

[fivemack]

Originally Posted by fetofs

Hi guys! I've been trying to implement various algorithms from number theory. In the AKS test, there is one step where it asks for the calculation of



Does this mean I have to reduce modulo X^r-1 first, then mod n?

What it means is that you should reduce the coefficients of the polynomial mod n, and reduce the polynomial itself by taking X^r=1.

Say you want (X+3)^37 mod (37, X^7-1)

(X+3)^2 = (X^2 + 6X + 9)
(X+3)^4 = (X^4 + 12*X^3 + 54*X^2 + 108*X + 81)
reduce mod 37: X^4 + 12*X^3 + 17*X^2 + 34*X +7
Now square that over the integers

X^8 + 24*X^7 + 178*X^6 + 476*X^5 + 1119*X^4 + 1324*X^3 + 1394*X^2 + 476*X + 49

reduce each term mod 37

X^8 + 24*X^7 + 30*X^6 + 32*X^5 + 9*X^4 + 29*X^3 + 25*X^2 + 32*X + 12

and reduce mod X^7-1, so X^8 = X, X^7 = 1, getting
30*X^6 + 32*X^5 + 9*X^4 + 29*X^3 + 25*X^2 + 33*X + 36

That's (X+3)^8; multiply by (X+3) to get
(X+3)^9 = 30*X^7 + 122*X^6 + 105*X^5 + 56*X^4 + 112*X^3 + 108*X^2 + 135*X + 108
Reduce mod X^7-1 first, getting
122*X^6 + 105*X^5 + 56*X^4 + 112*X^3 + 108*X^2 + 135*X + 138
and then reduce each term mod 37 getting
11*X^6 + 31*X^5 + 19*X^4 + 1*X^3 + 34*X^2 + 24*X + 27

Carry on to (X+3)^18, (X+3)^36 and (X+3)^37; but it is late and I am tired.

If you've got pari, the syntax is
? (Mod(1,37)*X+Mod(3,37))^9 % (X^7-1)
%1 = Mod(11, 37)*X^6 + Mod(31, 37)*X^5 + Mod(19, 37)*X^4 + Mod(1, 37)*X^3 + Mod(34, 37)*X^2 + Mod(24, 37)*X + Mod(27, 37)
? (Mod(1,37)*X+Mod(3,37))^37
%2 = Mod(1, 37)*X^37 + Mod(3, 37)
? %2 % (X^7+1)
%3 = Mod(36, 37)*X^2 + Mod(3, 37)

If you're doing polynomial-exponent by square-and-multiply, you never need to deal with anything of degree >2r or with coefficients larger than about n^2 ... you can reduce mod N or do the polynomial scrunching in whichever order you want.

You might want to read http://cr.yp.to/papers/aks.pdf , but it's fairly hairy.

[jasonp]

Originally Posted by fetofs

Hi guys! I've been trying to implement various algorithms from number theory. In the AKS test, there is one step where it asks for the calculation of



Does this mean I have to reduce modulo X^r-1 first, then mod n? If so, what is a good algorithm to reduce a polynomial modulo something (assume I already have addition, subtraction, multiplication, division, exponentiation)? I mean, I could do , but that seems too redundant.

See http://www.apple.com/acg/pdf/aks3.pdf