Re: finite fields info
- To: mathgroup at smc.vnet.net
- Subject: [mg5945] Re: [mg5854] finite fields info
- From: danl (Daniel Lichtblau)
- Date: Tue, 4 Feb 1997 00:05:18 -0500
- Organization: Wolfram Research, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
In article <5d2edt$ce5 at smc.vnet.net> stanica at acsu.buffalo.edu (Pantelimon
Stanica) writes:
> Hello, everyone!
>
> I would like to compute the function f(x)=Trace(x^(15)) defined on an
> extension of degree 8 of a field of char=2, i.e. Z_2. The field of
degree 8
> could be defined by the polynomial x^8+x^6+x^5+x^4+1 over Z_2.
> I would like to write the function as a string of 0,1. Can anyone help?
> I would appreciate any input.
> P. Stanica
>
Not sure I understand the question, but I'll take a stab at it. Given the
polynomial y=x^15 in the field Z_2/(x^8+x^6+x^5+x^4+1), find the minimal
polynomial of y, and return its penultimate coefficient. (Even if I am
wrong, maybe you will be able to adapt methods here to get what you want).
We will assume y has a minimum polynomial of degree exactly 8; clearly it
is no more than 8.
In[13]:= minpoly = x^8+x^6+x^5+x^4+1;
In[14]:= y = PolynomialMod[x^15, {minpoly,2}]
6 7
Out[14]= 1 + x + x
We will make the polynomial in y have leading coefficient 1, and have the
others initially indeterminant. We will solve for them presently.
In[15]:= coeffs = Map[c, Range[0,7]]
Out[15]= {c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7]}
In[16]:= newpoly = Append[coeffs,1] . Table[y^j, {j,0,8}]
6 7 8 6 7 6 7 2
Out[16]= (1 + x + x ) + c[0] + (1 + x + x ) c[1] + (1 + x + x ) c[2]
+
6 7 3 6 7 4 6 7 5
> (1 + x + x ) c[3] + (1 + x + x ) c[4] + (1 + x + x ) c[5] +
6 7 6 6 7 7
> (1 + x + x ) c[6] + (1 + x + x ) c[7]
In[17]:= reducedpoly = PolynomialMod[newpoly, {minpoly,2}]
2 4 6 6 7
Out[17]= x + x + x + c[0] + c[1] + x c[1] + x c[1] + c[2] + x c[2] +
2 3 5 6 7 3
> x c[2] + x c[2] + x c[2] + x c[2] + x c[2] + c[3] + x c[3] +
4 6 7 2 3
> x c[3] + x c[3] + x c[3] + x c[4] + x c[4] + x c[4] + c[5] +
3 4 5 2 3
> x c[5] + x c[5] + x c[5] + x c[5] + x c[6] + x c[6] + x c[6] +
4 6 7 3 5 7
> x c[6] + x c[6] + x c[6] + c[7] + x c[7] + x c[7] + x c[7] + x
c[7]
In[18]:= newcoeffs = CoefficientList[reducedpoly, x, Modulus->2]
Out[18]= {c[0] + c[1] + c[2] + c[3] + c[5] + c[7],
> c[2] + c[4] + c[5] + c[6] + c[7], 1 + c[2] + c[4] + c[6],
> c[2] + c[3] + c[4] + c[5] + c[6] + c[7], 1 + c[3] + c[5] + c[6],
> c[2] + c[5] + c[7], 1 + c[1] + c[2] + c[3] + c[6],
> c[1] + c[2] + c[3] + c[6] + c[7]}
We will convert the system to a matrix and vector pair, and use
LinearSolve with a Modulus of 2.
In[19]:= << LinearAlgebra`MatrixManipulation`
In[20]:= {lhs, rhs} = LinearEquationsToMatrices[Thread[newcoeffs==0],
coeffs]
Out[20]= {{{1, 1, 1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 1, 1, 1, 1},
> {0, 0, 1, 0, 1, 0, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 1},
> {0, 0, 0, 1, 0, 1, 1, 0}, {0, 0, 1, 0, 0, 1, 0, 1},
> {0, 1, 1, 1, 0, 0, 1, 0}, {0, 1, 1, 1, 0, 0, 1, 1}},
> {0, 0, -1, 0, -1, 0, -1, 0}}
In[21]:= soln = LinearSolve[lhs, rhs, Modulus->2]
Out[21]= {1, 1, 1, 0, 1, 0, 1, 1}
The minimal polynomial for y is Append[soln,1] . Table[y^j, {j,0,8}], and
the trace is the coefficient of the y^7 term, that is, 1.
Now check the result.
In[25]:= PolynomialMod[Append[soln,1] . Table[y^j, {j,0,8}], {minpoly,2}]
Out[25]= 0
Along the way, one really ought take the trouble to make sure minpoly is
really minimal:
In[22]:= Factor[x^8+x^6+x^5+x^4+1, Modulus->2]
4 5 6 8
Out[22]= 1 + x + x + x + x
Daniel Lichtblau
Wolfram Research
danl at wolfram.com