Jump to content

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

From Wikipedia, the free encyclopedia
Mathematics desk
< June 15 << May | June | Jul >> 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

[edit]

How to reduce a polynomial modulo using exponentation by squaring?

[edit]

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 (talkcontribs) 18:44, 16 June 2020 (UTC)[reply]

(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 bit means you can treat all polynomial coefficients as members of and therefore represent them by integers in the range . The bit means that all polynomials can be reduced to have degree less than , because since for . This means that all exponents can be treated as elements of .  --Lambiam 02:47, 17 June 2020 (UTC)[reply]