MathGroup Archive 2003

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

Search the Archive

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


  • Prev by Date: A numerical problem with ConstrainedMin
  • Next by Date: Another problem with ConstrainedMin
  • Previous by thread: Finite Fields and Polynomials
  • Next by thread: Wolfram Research Releases Control System Professional Suite