1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.)

$\endgroup$
8
  • $\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 torpor
    Mar 1 '19 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$ Mar 1 '19 at 17:27
  • $\begingroup$ I cannot open the package :-(. I got this error: Get::noopen: Cannot open AlgebraPolynomialPowerMod. $\endgroup$ Mar 1 '19 at 17:31
  • $\begingroup$ It's not documented because it is used directly by PolynomialMod. $\endgroup$ Mar 1 '19 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$ Mar 1 '19 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.