Finite Splitting Fields

Michael Monagan

This worksheet is an application of Maple to doing some simple calculations over finite fields GF(p^k).
The application is from error correcting codes and was brought to us by Nicolas Sendrier, INRIA, France, in May/90.
We were given a polynomial f(x) of the following form

> f := a -> 1+x^2+a*x^3+x^4;

where a = alpha was a given element in K = GF(2^17), and we were asked to determine if the polynomial f(alpha) splits into linear factors over K. It turned out that for the alpha we were given, the polynomial did not split. We were then asked to find an element a in K such that f(a) did split.

First let us define the field K(alpha) = GF(2^17) in Maple. We will represent the elements in K as polynomials in alpha where the minimial polynomial for alpha over GF(2) is this one (which was given to us)

> minpoly := y^17 + y^3 + 1;

We can check that this polynomial is irreducible over the ground field GF(2)

> Factor(minpoly) mod 2;

In Maple we represent the elements of a general finite field GF(p^k) as polynomials in alpha where alpha is a RootOf the minimal polynomial. And we use the alias command so that RootOf(minpoly) will print nicely as alpha

> alias( alpha = RootOf(y^17+y^3+1) ):

As an example, here is the inverse of alpha

> Normal(1/alpha) mod 2;

Thus our polynomial in x over K is

> f(alpha);

Our question is: does f(alpha) split over GF(2^17) into linear factors?
This can be answered by trying to factor f(alpha) and looking to see if all the factors are linear. But since we are only interested in the linear factors, we can just test to see how many roots the the polynomial has - which is more efficient.

> Roots(f(alpha)) mod 2;

This says that there are two roots each with multiplicity 1. So the polynomial did not split into linear factors. Note, another efficient way to test if a polynomial over a finite field factors into linear factors is to test if this condition holds

> Rem( x^(2^17), f(alpha), x ) = x;

But we better not try to compute this remainder because the input polynomial has degree 131072!! This calculation can be computed efficiently using the Powmod function which uses binary powering with remainder to compute this remainder. The idea is to compute this remainder as Rem( Rem( (131072)/2, f(alhpa), x )^2, f(alpha), x ). It is a good excercise to write a little program to do this and to determine the actual cost.

> Powmod(x,2^17,f,x) mod 2;

Now the next question was to try to find an element a of GF(2^17) such that f(a) splits into linear factors. We do this by simply trying a random polynomial in alpha (of degree 16 or less) until we find a good one. Here is a little loop to do this

> do

> a := subs( y=alpha, Randpoly(16,y) mod 2 );

> if Powmod( x, 2^17, f(a), x ) mod 2 = x then print(a); break fi;

> od;

A final check

> Roots(f(a)) mod 2;

Thus our polynomial is

> f(a);

For the interested reader, the Roots function uses a probabilistic method to compute the roots of a polynomial over a finite field. The idea is very nice. Consider a polynomial in x over GF(p) where p is prime. We know from Fermat's little theorem that the following is true

> 'a^p = a mod p';

This means that the polynomial x^p-x has roots 0,1,...,p-1 over GF(p), i.e. it factors as follows

> x^p-x = Product( x-i, i=0..p-1 );

So suppose we are given a polynomial a(x) and we want to compute the roots. We can compute the product of all the linear factors by computing the g = Gcd( a(x), x^p-x ). This Gcd calculation needs to be computed carefully if p is large. So the next thing to do is to split g into the linear factors to get the roots. Here comes the probabilistic part of the algorithm. We know that we can write (assuming p is an odd prime)

> x^p-x = x*(x^((p-1)/2)-1) * (x^((p-1)/2)+1);

Ignoring the factor of x, consider now the following calculations

> 'g1 = Gcd( a(x), x^((p-1)/2)-1 ) mod p', 'g2 = Gcd(a(x), x^((p-1)/2)+1) mod p';

These two calculations will with good probability split the product of linear factors g into two parts. The next idea is instead of computing these Gcd's, to choose an element beta at random from GF(p) and compute using x = x+beta instead. The polynomial (x+beta)^((p-1)/2)-1 will now be a product of different linear factors. The idea then is to do the above Gcd calculation for g1 with different beta's until you get a non-trivial splitting of g. Repeat on each factor of g until g is completely split into linear factors. That's the idea. One can show that the idea generalizes to arbitrary finite fields GF(p^k) and a similar idea can be used to handle the special case p=2.

>

>

>

>