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`

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

```

• Prev by Date: Re: Changing Plot3D to polygons?
• Next by Date: Re: Help me:Statistic-Multivareate Analysis
• Previous by thread: finite fields info
• Next by thread: 3.0 Installation Problem