Maple User Group Answers

[Anfang] [Hauptseite] [Suchen] [LDFM]

Irreducibility in algebraically closed fields with char > 0   (14.3.00)

Nivaldo Nunes de Medeiros Junior

I want to test if a polynomial in two variables is or not irreducible over the algebraic closure of F_2, the Galois Field with two elements. If possible, I want also its factors. Is there some way to do this with Maple VR5? Thanks in advance,

David Joyner   (21.3.00)

1. I think the answer is "you can't".

2. What you *can* probably do is factor over larger and larger extensions. If you type

?Factor 

you'll see the syntax of how to add extensions. *You* will have to come up with an irreducible polynomial yourself. For example,

Irreduc(x^8+x^7+x^6+x+1) mod 2;
alias(tau=RootOf(x^8+x^7+x^6+x+1) mod 2):
Factor(x^2+2*x*y+y^2+1+x+y,tau) mod 2;

3. There are routines in the little fields package I wrote, at

http://web.usna.navy.mil/~wdj/ffield0.htm

which might help.

4. You could also try something like

evala(Divide(x^2-y,x-sqrt(y),'q'));

Type ?Divide for more syntax information.

J H Davenport   (22.3.00)

However, there is a fairly simple way of doing it.

1) Choose a value a of y such that f(x,a) remains sqfr mod 2 Note that you may have to move to an extension field to do this.

2) Let K be the splitting field of f(x,a)

3) Factor f(x,y) over K

Mike May, S.J.   (22.3.00)

As some other people have noted, there is no easy way to do this. It can however be done.

First the mathematics:

The trick is to note that any polynomial that factors over the algebraic closure of GF(2) must also factor over GF(2^n) for some n. Thus all we have to do is find an upper bound for the value of n to test. We also note that if the polynomial f(x,y) has coefficients in GF(2), and factors in with a coefficient gamma in GF(2^n) but not in any smaller finite field, then f(x,y) must have the n conjugate factors under the automorphism that generates the Galois group of GF(2^n) over GF(2). Thus the minimum of the degrees of f in x and y gives an upper bound for the n we need to use.

Now for the Maple part (done with version V5):

Suppose that we want to factor f(x,y) over GF(2^12). We want to load the GF package for doing Galois fields, then call it for GF(2^12). We want Maple to find the polynomial used for the extension which we will designate as p1. Use alias to make alpha the root of p1. Then we factor f over GF(2^12) with the command

Factor(f, alpha) mod 2;

Putting this together we get

> readlib(GF);
> GF1 := GF(2, 12):
> `?` := Z;
> p1 := GF1[ConvertOut](GF1[extension]);
> alias(alpha=RootOf(p1));f := x^16+x^15+x^14+x^13+x^12+x^11+1;
> Factor(f) mod 2;
> Factor(f, alpha) mod 2;
> g := x^7+y^7;
> Factor(g) mod 2;
> Factor(g, alpha) mod 2;

In fact, g splits over GF(2^3), hence also over GF(2^12).

2 warnings:

1) When I tried putting the code above into a loop for various values of n in GF(2,n), I got strange results.

2) A polynomial could have 3 factors that show up in GF(2^3) and 5 that show up in GF(2^5), thus being a polynomial of degree 8 that splits for the first time in GF(2^15).

[Anfang] [Hauptseite] [Suchen] [LDFM]