[Date Index] [Thread Index] [Author Index]

Re: Polynomial Reduction with Mod

• To: mathgroup at smc.vnet.net
• Subject: [mg30440] Re: [mg30436] Polynomial Reduction with Mod
• From: Ken Levasseur <Kenneth_Levasseur at uml.edu>
• Date: Sun, 19 Aug 2001 02:01:34 -0400 (EDT)
• References: <200108180804.EAA22597@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Flip:

If you want to do something involving polynomials and don't know the
name of the function that might do it, try doing  this.

In[1]:=
?*Polynomial*

CharacteristicPolynomial PolynomialQ
InterpolatingPolynomial  PolynomialQuotient
PolynomialForm           PolynomialReduce
PolynomialGCD            PolynomialRemainder
PolynomialLCM            Polynomials
PolynomialMod

You might think that it's PolynomialMod that does what you want, but
since modular calculations are remainders, PolynomialRemainder is the
one.  You would see that by executing ?PolynomialMod you get a different
result.

In[2]:=
?PolynomialRemainder

\!\(TraditionalForm\`"PolynomialRemainder[p, q, x] gives the remainder
from \
dividing p by q, treated as polynomials in x."\)


In[3]:=
PolynomialRemainder[1 + x^3 + x^4 + x^5 + x^6 + x^8 + x^11 +
   x^13, 1 + x + x^3 + x^4 + x^8, x]

Out[3]=
-x^7 - x^6 + x^5 + x^4 + x^2 + x + 1


If you want your coefficients to be elements of a finite field, like the
integers mod 2, you can use the AbstractAlgebra packages at
http://www.central.edu/eaam.html

In[9]:=
Needs["AbstractAlgebra`Master`"]

In[17]:=
p = Poly[ZR[2], 1 + x^3 + x^4 + x^5 + x^6 + x^8 + x^11 + x^13];

In[18]:=
q = Poly[ZR[2], 1 + x + x^3 + x^4 + x^8];

In[19]:=
R = PolynomialsOver[ZR[2]]

Out[19]=
\!\(TraditionalForm\`"-Ring of Polynomials over Z[2]-"\)

In[20]:=
PolynomialRemainder[R, p, q]

Out[20]=
x^7 + x^6 + x^5 + x^4 + x^2 + x + 1

This could be done without the AbstractAlgebra packages using
PolynomialMod, but the packages contain a lot of other things.

Ken Levasseur
Math Sciences
UMass Lowell


Flip at safebunch.com wrote:

> Hello,
>
> Is Mathematica capable of calculating this type of problem?
>
> Mod[1 + x^3 + x^4 + x^5 + x^6 + x^8 + x^11 + x^13,
> 1 + x + x^3 + x^4 + x^8]
>
> The second polynomial is irreducible?
>
> By the way, the soultion is: x^7 + x^6 + 1.
>
> Thank you for any inputs ...

• References:
  • Polynomial Reduction with Mod
    • From: Flip@safebunch.com