Re: algebra problem, need help fast!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg14783] Re: algebra problem, need help fast!!!
- From: Daniel Lichtblau <danl>
- Date: Sat, 14 Nov 1998 03:08:11 -0500
- Organization: Wolfram Research, Inc.
- References: <720rkt$1ob@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Base_D wrote:
>
> Does anyone know how to use mathematica to find all the subfields the
> following field:
>
> K = Z/2Z[X]/(f) where is an irreducible polynomial of degree 5.
>
> Any help would be greatly appreciated. Rick
I guess I should first note that since 5 is prime there are no proper
subfields of Z/(2) extended by a fifth degree (irreducible) polynomial.
This follows from the fact that 2^5-1 is prime (31).
Below is some Mathematica code to do some relevant computations with
finite fields. I'll demonstrate with the prime characteristic p = 293
and an extension of degree deg = 15.
Problem 1: How do we obtain such an extension?
For this we will need a polynomial of degree 15 that is irreducible mod
293.
p = 293;
deg = 15;
randpoly[x_, deg_] := Table[Random[Integer,{0,p-1}], {deg}] .
Table[x^j, {j,0,deg-1}] + x^deg
SeedRandom[1111]
getIrreducible[x_, deg_, prime_] := Module[{poly},
While [True,
poly = randpoly[x, deg];
If [Length[FactorList[poly,Modulus->p]] == 2, Return [poly]];
]
]
With this we can do:
In[162]:= InputForm[irred = getIrreducible[x, deg, p]]
Out[162]//InputForm=
38 + 117*x + 244*x^2 + 234*x^3 + 212*x^4 + 142*x^5 + 103*x^6 +
60*x^7 + 203*x^8 + 124*x^9 + 183*x^10 + 96*x^11 + 225*x^12 +
123*x^13 + 251*x^14 + x^15
Now we have the field F = Z[x]/(p,irred). I'll briefly outline on how
one might do arithmetic in this field. You can represent elements as
polynomials of degree 14 with coefficients in Z/(p) (read: "integers
modulo p"). Adding is cooeficient-wise, then take these modulo p. For
multiplication one must reduce the result modulo the defining
polynomial (the one we call "irred" above) and p.
To find subfields it will help to have an element that generates the
multiplicative cyclic group F* (non-zero elements of F). These are (I
think) called primitive elements, hence the naming conventions in the
below code.
Problem 2: How do we find such a generator for F*?
Below is some code to do this. We need to find an element y such that
y^((p^deg)-1) == 1 mod {irred,p} and
y^((p^smallerdeg)-1) != 1 mod {irred,prime} for any smallerdeg < deg. It
suffices to check only the largest proper divisors of (p^deg)-1). To
this end I required FactorInteger which can be quite slow for numbers
larger than, say, 35 digits. I do not know if one can avoid integer
factorization to find such a cyclic generator. We'll also need
efficient way to raise one polynomial to a power modulo another
polynomial (and a prime), hence we load the standard add-on package
PolynomialPowerMod.
I only look for linear generators of F*. I am not sure offhand if this
is always sufficient to find a generator.
<<Algebra`PolynomialPowerMod`;
isPrimitive[lin_, poly_, prime_, deg_, facs_] := Module[{},
For [j=1, j<=Length[facs], j++,
If [PolynomialPowerMod[lin,facs[[j]],{poly,p}]===1,
Return [False]];
];
True
]
getprim[x_, poly_, prime_, deg_] := Module[
{j, facs=(p^deg-1)/Map[First,FactorInteger[p^deg-1]]},
For [j=0, j<prime, j++,
If [isPrimitive[x+j, poly, prime, deg, facs], Throw[x+j]]];
Throw[$Failed]
]
getPrimitiveGenerator[x_, poly_, prime_, deg_] :=
Catch[getprim[x, poly, prime, deg]]
So we now do
In[178]:= Timing[primpoly = getPrimitiveGenerator[x, irred, p, deg]]
Out[178]= {56.05 Second, 2 + x}
Note that this is not terribly fast (timings from a PPro 200 under
Linux).
Problem 3: Now that we have a generator y (= x+2) of F*, how do we use
it to obtain proper subfields?
General theory tells us that there will be proper subfields of order p^d
for all divisors d of deg. Some reasoning leads us to the fact that we
obtain these from powers of our generator y. Specifically, for each d
dividing deg, we get a subfield whose cyclic multiplicative group is
generated by y^(p^deg-1)/(p^d-1). In this case there would be two such
generators (one for d=3 and one for d=5):
y^400323847030642761744857730301
and
y^4663115832633535770588943
Problem 4: Now that we have generators for the cyclic groups, how might
we obtain the minimum polynomials satisfied by these generators?
Take a generator gen for a given d. We know the minimum polynomial will
have the form
a[0] + a[1]*gen + a[2]*gen^2 + .... + a[d]*gen^d We just reduce this
thing modulo {irred,p}, set each coefficient of the polynomial so
obtained to zero. This gives an overdetermined by consistent system of
linear equations which we then solve mod p. We then return the
appropriate polynomial, reusing the variable with which we defined the
original extension (confusing, but a common thing to do all the same).
minPoly[x_, gen_, bigdeg_, smalldeg_, irred_, prime_] := Module[
{a, vars, newpoly, redgen, polys, order, sol, rhs},
a[smalldeg] = 1;
vars = Array[a, smalldeg, 0];
order = (p^bigdeg-1)/(p^smalldeg-1);
redgen = PolynomialPowerMod[gen, order, {irred,p}];
newpoly = a[0] + Sum[a[j]*
PolynomialPowerMod[redgen, j, {irred,p}], {j,smalldeg}];
polys = CoefficientList[newpoly, x, Modulus->prime];
mat = Outer[D, polys, vars];
rhs = -polys /. Thread[vars->0];
sol = LinearSolve[mat, rhs, Modulus->prime];
x^smalldeg + sol.x^Range[0,smalldeg-1]
]
In[185]:= dlist = Map[First,FactorInteger[deg]] Out[185]= {3, 5}
In[187]:= InputForm[Timing[minpolys =
Table[minPoly[x, primpoly, deg, dlist[[j]], irred, p],
{j,Length[fax]}]]]
Out[187]//InputForm=
{9.009999999999991*Second, {261 + 157*x + 285*x^2 + x^3,
261 + 238*x + 275*x^2 + 67*x^3 + 230*x^4 + x^5}}
Daniel Lichtblau
Wolfram Research