MathGroup Archive 2003

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

Search the Archive

Finite Fields and Polynomials

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

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

  • Prev by Date: Re: simple question if/while loop
  • Next by Date: Wolfram Research Releases Control System Professional Suite
  • Previous by thread: Running 4.0.1 under MacOSX-Classic?
  • Next by thread: Re: Finite Fields and Polynomials