Finite Fields and Polynomials

*To*: mathgroup at smc.vnet.net*Subject*: [mg40140] Finite Fields and Polynomials*From*: "flip" <flip_alpha at safebunch.com>*Date*: Sat, 22 Mar 2003 05:08:41 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

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? 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?). 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".

**Follow-Ups**:**Re: Finite Fields and Polynomials***From:*Daniel Lichtblau <danl@wolfram.com>