Re: Finite Fields and Polynomials

*To*: mathgroup at smc.vnet.net*Subject*: [mg40156] Re: [mg40140] Finite Fields and Polynomials*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sun, 23 Mar 2003 04:12:33 -0500 (EST)*References*: <200303221008.FAA22757@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

flip wrote: > > Hello (please excuse the long post, but I think this is a very easy question > for someone who has done this sort of thing with Mathematica), > > Is there a way in Mathematica to show the following? The topic is Finite > Fields and Polynomials. I'll give detailed examples and I believe > Mathematica can do this sort of thing, I'm just not sure how. > > 1. Let F be the field Z{2} = {0, 1}; then f = x^2 + x + 1 is an irreducible > polynomial of degree 2 over Z{2}. Hence Z{2}[x ]/ (x^2+x+1) is a field > whose elements can be represented in the form a + b*alpha, a, b elements > Z{2}, where alpha satisifes f(alpha) = 0, so alpha^2 + alpha+1=0, which > menas that alpha^2 = alpha + 1. > > Hence Z{2}[x] / (x^2 + x + 1) is a field with four elements: Z{2}[x] / (x^2 > + x + 1) = {0, 1, alpha, 1 + alpha}. > > Can Mathematica show this, that is find the irreducible polynomial of "some > degree chosen by the user" and then generate the elements of the field? > > 2. We determine the elements of F{2^3}, states F-sub-2^3. > > a. If we regard F{2^3} as a simple extension of degree 3 of the prime field > F{2}, then this extension is obtained by adjoining to F{2} a root of an > irreducible cubic polynomial over F{2}. > > It is easily verified that x^3 + x + 1 and x^3 + x^2 + 1 are irreducible > over F{2} (can Mathematica give me these orreducibles?). > > Therefore F{2^3} is isomorphic F{2}[x] / (x^3 + x + 1) and also F{2^3} is > isomorphic F{2}[x] / (x^3 + x^2 + 1) . > > Let alpha be a root of f = x^3 + x + 1, then 1, alpha, alpha^2 form a basis > of F{2^3} over F{2}. > > The elements of F{2^3} are of the form a + b*alpha + c*alpha^2 for all a, b, > c, elements of F{2} with alpha^3 + alpha + 1 = 0 (see 1. above for example). > I'd like to be able to show that list (table) in Mathematica, is there a command or > set of commands? The code below should get you started. randomPoly[deg_, mod_, x_] := x^deg + Table[Random[Integer,{0,mod-1}], {deg}] . x^Range[0,deg-1] randomIrreduciblePoly[deg_, mod_, x_] := Module[{defpoly}, While[Length[FactorList[defpoly=randomPoly[deg,mod,x]]]!=2]; defpoly ] You can also generate all monic polynomials of given degree and modulus, and test each for irreducibility. This will be costly if degree and/or modulus is large. To generate the elements you don't even need to know the irreducible (you will need it for multiplication). elements[deg_, mod_, x_] := Flatten[Outer[List,Apply[Sequence,Table[Range[mod]-1,{deg}]]],deg-1] . x^Range[0,deg-1] Note that for large fields you'd not want to do this. Also note that you can just as well represent them by the integer vectors. > b. We could also use g = x^3 + x^2 + 1 to determine the elements of F{2^3}. > Let beta be a root of root of g, so Beta^3 + beta^2 + 1 = 0. > > It can easily be verified that beta + 1 is a root of f in F{2}[x] / (g) (can > Mathematica just find that root?). Start with the assumption that the root is linear in beta. betaplus = beta+a; Form the polynomial that we desire to set to zero. Reduce it by the defining polynomial for beta. zero = Last[PolynomialReduce[betaplus^3+betaplus+1, beta^3 + beta^2 + 1, {beta,a}, Modulus->2]] Now solve for the undetermined coefficient 'a'. a /. SolveAlways[{zero==0, Modulus==2}, beta] > The two fields F{2}[x] / (f) and F{2}[x] / (g) are splitting fields of > x^8 - x and are thus isomorphic. Therefore, there is an isomoprhism psi > such that psi(alpha) = beta + 1 and psi restricted to F{2} is the identity > mapping. > > The elements 1, beta + 1, (beta + 1)^2 for a basis of F{2}[x] / (g) over > F{2} (can we show this in Mathematica)? Thus, the isopmorphism psi is given by psi(a > + b*alpha + c*alpha^2) = a + b(beta + 1) + c(beta + 1)^2 with a, b, c, > elements of F{2}. > > Then showing the mulitplication table of the multiplicative group F{2}[x] / > (x^3 + x^2 + 1)\{0} (can Mathematica show that?), we can arrive at: > > F{2}[x] / (g) = {0, 1, beta, beta+1, beta^2, beta^2+beta, beta^2+1, > b^2+beta+1} = {0, 1, beta, beta^2, beta^3, beta^4, beta^5, beta^6} with > beta^3 = beta^2 + 1 and beta^7 = 1. > > Basically, can these sorts of things be found in Mathematica and shown using table? > > Thank you for any thoughts and pointers, Flip > > To email me, remove "_alpha". You can do multiplication of field elements simply by multiplying the polynomials and then reducing via PolynomialMod[poly, {definingpolynomial, mod}] For example: In[94]:= PolynomialMod[(1+beta+beta^2)*(1+beta^2), {beta^3 + beta^2 + 1,2}] Out[94]= 1 Setting up a table is just a matter of iterating over all pairs of elements with this operation. If so desired, you can also find a multiplicative representation via a primitive (as opposed to merely irreducible) defining polynomial. See, for example, http://forums.wolfram.com/mathgroup/archive/1998/Nov/msg00194.html Daniel Lichtblau Wolfram Research

**References**:**Finite Fields and Polynomials***From:*"flip" <flip_alpha@safebunch.com>