Re: Working with polynomials in Z/23
- To: mathgroup at smc.vnet.net
- Subject: [mg106579] Re: [mg106566] Working with polynomials in Z/23
- From: danl at wolfram.com
- Date: Sun, 17 Jan 2010 07:10:31 -0500 (EST)
- References: <201001161113.GAA21811@smc.vnet.net>
> I'm exploring polynomials over integer values modulo 23 (i.e. 'x' in
> the polynomial can only take integer values, and my polynomials only
> have integer coefficients). I know that I can reduce the polynomial
> coefficients mod 23 using PolynomialMod. However, I also want to
> reduce the exponents for the identity x^23 = x. Is there an easy way
> to do that?
>
> For example, if I have the polynomial P(x) = x^5 + 2x. Then
> P(P(x)) = x^25 + 10x^21 + 40x^17 + 80x^13 + 80x^9 + 34x^5 + 4x.
> PolynomialMod will reduce this to
> P(P(x)) = x^25 + 10x^21 + 17x^17 + 11x^13 + 11x^9 + 11x^5 + 4x.
> But since x^25 = x^3, the answer I want is
> P(P(x)) = 10x^21 + 17x^17 + 11x^13 + 11x^9 + 11x^5 + x^3 + 4x.
>
> I tried to figure out a way to do this using CoefficientList, but I'm
> not proficient enough as an occasional Mathematica user to figure out
> how to sort of "fold" the list onto itsefl and sum the columns.
>
> Any help would be appreciated,
> Bob H
PolynomialMod will handle a polynomial as well as integer modulus; this is
mentioned in the Documentation Center under PolynomialMod.
p[x_] := x^5 + 2*x
In[40]:= PolynomialMod[p[p[x]], {x^23 - x, 23}]
Out[40]= 4 x + x^3 + 11 x^5 + 11 x^9 + 11 x^13 + 17 x^17 + 10 x^21
For more flexibility one could instead use PolynomialReduce. (Better
handling for multivariate situations, term ordering, etc.). Not really
needed for the sort of example you indicate, but it might be done as
below.
In[41]:= Last[PolynomialReduce[p[p[x]], x^23 - x, x, Modulus -> 23]]
Out[41]= 4 x + x^3 + 11 x^5 + 11 x^9 + 11 x^13 + 17 x^17 + 10 x^21
Daniel Lichtblau
Wolfram Research
- References:
- Working with polynomials in Z/23
- From: me13013 <me13013@gmail.com>
- Working with polynomials in Z/23