This is documentation for Mathematica 3, which was
based on an earlier version of the Wolfram Language.
 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]:= < 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]=