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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < June 15 ! width="25%" align="center"|<< May | June | Jul >> ! width="20%" align="right" |Current desk > |}

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{m}\mathrm{o}\mathrm{d}n)$ bit means you can treat all polynomial coefficients as members of ${𝐙}_n$ and therefore represent them by integers in the range $0..n-1$. The $(\mathrm{m}\mathrm{o}\mathrm{d}{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{m}\mathrm{o}\mathrm{d}{x}^r-1)$ since $x^s=x^{s-r}(x^r-1)+x^{s-r}$ for $s\ge r$. This means that all exponents can be treated as elements of ${𝐙}_r$.  --Lambiam 02:47, 17 June 2020 (UTC)