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