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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.)

Improve this answer
$\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 missing motivation ♦
    Commented 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
    Commented Mar 1, 2019 at 17:27
  • $\begingroup$ I cannot open the package :-(. I got this error: Get::noopen: Cannot open AlgebraPolynomialPowerMod. $\endgroup$
    – azerbajdzan
    Commented Mar 1, 2019 at 17:31
  • $\begingroup$ It's not documented because it is used directly by PolynomialMod. $\endgroup$
    – Daniel Lichtblau
    Commented 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
    Commented Mar 1, 2019 at 23:01
2
$\begingroup$

According to the documentation from Wolfram,

Algebra`PolynomialPowerMod

The functionality of PolynomialPowerMod is now available in the kernel function PolynomialRemainder. Modulus is now an option to the kernel functions PolynomialQuotient and PolynomialRemainder.

I believe it is now possible to avoid this undocumented function Algebra`PolynomialPowerMod`PolynomialPowerMod[] by doing

PolynomialRemainder[(-1 + x + x^2 - x^4 + x^6)^5, x^3 + 1, x]
70 + 79 x + 8 x^2
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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