Wikipedia:Reference desk/Archives/Mathematics/2020 June 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 16

How to reduce a polynomial modulo using exponentation by squaring?

I try to understand how does the AKS primality test work and I was told that I need to reduce to polynomial (x+a)^n-(x^n+a) modulo (n,x^r-1) using exponentation by squaring, but I don't understand how I can use it. Could anyone please explain this to me? Thanks! — Preceding unsigned comment added by Uri Gluck (talk • contribs) 18:44, 16 June 2020 (UTC)

(In haste.) For a start, see the article Exponentiation by squaring. The article Modular arithmetic has near the end a C function implementing this in modular arithmetic, but the logic is the same for any ring; notice that you only need modular reduction for the multiplication operation. The $(\mathrm {mod} ~n)$ bit means you can treat all polynomial coefficients as members of $\mathbf {Z} _{n}$ and therefore represent them by integers in the range $0..n{-}1$. The $(\mathrm {mod} ~x^{r}{-}1)$ bit means that all polynomials can be reduced to have degree less than $r$, because $x^{s}\equiv x^{s-r}~(\mathrm {mod} ~x^{r}{-}1)$ since $x^{s}=x^{s-r}(x^{r}{-}1)+x^{s-r}$ for $s\geq r$. This means that all exponents can be treated as elements of $\mathbf {Z} _{r}$.  --Lambiam 02:47, 17 June 2020 (UTC)