# Polynomial PowerMod

Is there equivalent of PowerMod for polynomials in Mathematica?

We have Mod[a^e,m]==PowerMod[a,e,m], $$a$$, $$e$$ and $$m$$ all integers.

PowerMod is much more efficient for large $$e$$.

We have also PolynomialMod[p1^e,p2], $$p1$$ polynomial, $$e$$ integer, $$p2$$ integer or polynomial.

For large $$e$$ it is inefficient.

Something like PolynomialPowerMod would be useful. Is there something like it? Or I have to write my own procedure?

There is an undocumented function for this purpose: AlgebraPolynomialPowerModPolynomialPowerMod[]. For example, one could do

AlgebraPolynomialPowerModPolynomialPowerMod[-1 + x + x^2 - x^4 + x^6, 5, x, x^3 + 1]
70 + 79 x + 8 x^2


which gives the same result as

PolynomialMod[(-1 + x + x^2 - x^4 + x^6)^5, x^3 + 1]
70 + 79 x + 8 x^2


(I previously used the function in this answer for computing a modular inverse.)

• (Could a kind soul please evaluate the code snippet I gave, so that other people can see the expected result?) Mar 1 '19 at 17:17
• I wonder why it is undocumented? Such a useful function. I was trying to write my own but it was not much efficient. Mar 1 '19 at 17:27
• I cannot open the package :-(. I got this error: Get::noopen: Cannot open AlgebraPolynomialPowerMod. Mar 1 '19 at 17:31
• It's not documented because it is used directly by PolynomialMod. Mar 1 '19 at 17:48
• Per J.M.'s request to run the snippet: AlgebraPolynomialPowerModPolynomialPowerMod[-1 + x + x^2 - x^4 + x^6, 5, x, x^3 + 1] gives 70 + 79 x + 8 x^2 as does PolynomialMod[(-1 + x + x^2 - x^4 + x^6)^5, x^3 + 1] Mar 1 '19 at 23:01