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