This is documentation for Mathematica 3, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)
 Documentation / Mathematica / Add-ons / Standard Packages / Algebra  /

Algebra`PolynomialPowerMod`

This package introduces the function PolynomialPowerMod, which efficiently computes a power of a polynomial modulo a prime and a polynomial. Support for the Modulus option is added to PolynomialQuotient and PolynomialRemainder. The package also extends the Modulus option of Factor, FactorList, and PolynomialGCD to handle large prime moduli.
The factoring algorithm used by the functions in this package is described in D.E. Knuth, Seminumerical Algorithms, Addison-Wesley, 1981, Section 4.6.2. One first uses the derivative to factor the polynomial in into square-free factors. The degree factorization of modulo is obtained by finding the greatest common denominator of and for . This is computed quickly using repeated squaring. Finally, one uses the probabilistic factoring algorithm of Cantor-Zassenhaus to factor the result into irreducible degree

factors.


Using PolynomialPowerMod.

  • This loads the package.
  • In[1]:= <<Algebra`PolynomialPowerMod`

  • The package function PolynomialPowerMod is more efficient than the built-in function PolynomialMod applied to a polynomial raised to a power.
  • In[2]:= {Timing[PolynomialPowerMod[1 + x, 200,
    {x^3 + x^2 + 1, Prime[4750]}]][[1]],
    Timing[PolynomialMod[(1 + x)^200,
    {x^3 + x^2 + 1, Prime[4750]}]][[1]]}

    Out[2]=


    Modulus option for PolynomialQuotient and PolynomialRemainder.

  • Here are two polynomials in

    .
  • In[3]:= {f, g} = {(1 + x)^3 (1 + x^3), x^2 + 2};

  • Using the Modulus option of PolynomialQuotient is equivalent to applying PolynomialMod to the result of PolynomialQuotient.
  • In[4]:= {PolynomialQuotient[f, g, x, Modulus -> 11],
    PolynomialMod[PolynomialQuotient[f,g,x], 11]}

    Out[4]=

  • Using the Modulus option of PolynomialRemainder is equivalent to applying PolynomialMod to the result of PolynomialRemainder.
  • In[5]:= {PolynomialRemainder[f, g, x, Modulus -> 11],
    PolynomialMod[PolynomialRemainder[f,g,x],11]}

    Out[5]=


    Extending PolynomialGCD, Factor, and FactorList to accept large prime moduli.

  • Using the Modulus option with PolynomialGCD is equivalent to applying PolynomialMod to the result of PolynomialGCD.
  • In[6]:= {PolynomialGCD[x^2-1,x-1, Modulus -> Prime[10^8]],
    PolynomialMod[PolynomialGCD[x^2-1,x-1], Prime[10^8]]}

    Out[6]=

  • After loading this package, a polynomial may be factored modulo a large prime.
  • In[7]:= Factor[1 + 2 x^3, Modulus -> Prime[10^7]]

    Out[7]=