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$
3
$\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$
  • $\begingroup$ (Could a kind soul please evaluate the code snippet I gave, so that other people can see the expected result?) $\endgroup$ – J. M. will be back soon Mar 1 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 at 17:27
  • $\begingroup$ I cannot open the package :-(. I got this error: Get::noopen: Cannot open AlgebraPolynomialPowerMod. $\endgroup$ – azerbajdzan Mar 1 at 17:31
  • $\begingroup$ It's not documented because it is used directly by PolynomialMod. $\endgroup$ – Daniel Lichtblau Mar 1 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$ – Christopher Lamb Mar 1 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.