I'm trying to write a Python program for the AKS primality test.
The 5th step states if (X+a)^n≠ X^n+a (mod X^r − 1,n), output composite; but I'm not sure what to do when the modulo has 2 arguments: Xr-1 and n. In this case, what is it supposed to be calculating?
I understand a(mod b) means that the remainder after dividing a number with b = a, but not sure what the 2 arguments in this are meant to mean.
The X here means that we're working with polynomials. Mod X^r - 1 means that we mod all of the polynomial exponents by r. Mod n means that we mod all of the coefficients by n.
As an example, if we have a polynomial X^4 + 4 X^3 + 6 X^2 + 4 X + 1 and we're modding by X^3 - 1 (i.e., r = 3) and n = 5, then we get
X^4 + 4 X^3 + 6 X^2 + 4 X + 1 -> (mod by X^3 - 1)
X^1 + 4 X^0 + 6 X^2 + 4 X + 1 =
X + 4 + 6 X^2 + 4 X + 1 =
6 X^2 + 5 X + 5 -> (mod by 5)
1 X^2 + 0 X + 0 =
X^2.