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>
- Re: Finite Fields and Polynomials