Polynomial PowerMod

Question

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?

2 revs · Accepted Answer · 2019-03-02 20:03:41Z

4

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

Algebra`PolynomialPowerMod`PolynomialPowerMod[-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.)

community wiki

$\begingroup$ (Could a kind soul please evaluate the code snippet I gave, so that other people can see the expected result?) $\endgroup$
– J. M.'s eventual burnout ♦
Mar 1, 2019 at 17:17
$\begingroup$ I wonder why it is undocumented? Such a useful function. I was trying to write my own but it was not much efficient. $\endgroup$
– azerbajdzan
Mar 1, 2019 at 17:27
$\begingroup$ I cannot open the package :-(. I got this error: Get::noopen: Cannot open AlgebraPolynomialPowerMod. $\endgroup$
– azerbajdzan
Mar 1, 2019 at 17:31
$\begingroup$ It's not documented because it is used directly by PolynomialMod. $\endgroup$
– Daniel Lichtblau
Mar 1, 2019 at 17:48
1

$\begingroup$ 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] $\endgroup$
– Rabbit
Mar 1, 2019 at 23:01

| Show 3 more comments

1 Answer 1