MathGroup Archive 1997

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

Search the Archive

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



  • 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