       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:= minpoly = x^8+x^6+x^5+x^4+1;

In:= y = PolynomialMod[x^15, {minpoly,2}]
6    7
Out= 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:= coeffs = Map[c, Range[0,7]]
Out= {c, c, c, c, c, c, c, c}

In:= newpoly = Append[coeffs,1] . Table[y^j, {j,0,8}]
6    7 8                6    7               6    7 2
Out= (1 + x  + x )  + c + (1 + x  + x ) c + (1 + x  + x )  c
+

6    7 3              6    7 4              6    7 5
>    (1 + x  + x )  c + (1 + x  + x )  c + (1 + x  + x )  c +

6    7 6              6    7 7
>    (1 + x  + x )  c + (1 + x  + x )  c

In:= reducedpoly = PolynomialMod[newpoly, {minpoly,2}]
2    4    6                  6         7
Out= x  + x  + x  + c + c + x  c + x  c + c + x c +

2         3         5         6         7                3
>    x  c + x  c + x  c + x  c + x  c + c + x  c +

4         6         7                  2         3
>    x  c + x  c + x  c + x c + x  c + x  c + c +

3         4         5                  2         3
>    x c + x  c + x  c + x  c + x c + x  c + x  c +

4         6         7                         3         5         7
>    x  c + x  c + x  c + c + x c + x  c + x  c + x
c

In:= newcoeffs = CoefficientList[reducedpoly, x, Modulus->2]
Out= {c + c + c + c + c + c,

>    c + c + c + c + c, 1 + c + c + c,

>    c + c + c + c + c + c, 1 + c + c + c,

>    c + c + c, 1 + c + c + c + c,

>    c + c + c + c + c}

We will convert the system to a matrix and vector pair, and use
LinearSolve with a Modulus of 2.

In:= << LinearAlgebra`MatrixManipulation`

coeffs]

Out= {{{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:= soln = LinearSolve[lhs, rhs, Modulus->2]
Out= {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:= PolynomialMod[Append[soln,1] . Table[y^j, {j,0,8}], {minpoly,2}]
Out= 0

Along the way, one really ought take the trouble to make sure minpoly is
really minimal:

In:= Factor[x^8+x^6+x^5+x^4+1, Modulus->2]
4    5    6    8
Out= 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