How to work in GAP with finite fields given by a particular polynomial.

Question

I need help, I'm working over the Galois Fields $\mathrm{GF}(2^m)$ and I will construct the field with a chosen irreducible polynomial of degree $m$ over $\mathrm{GF}(2)$. I can do it on GAP. Now comes my problem. I'll take $a$ to be a root of this polynomial and I need to find, for a fixed $c$ in $GF(2^m)$, an expression for $c$ in terms of the field $F[a]$ that I constructed. Is it possible to do it in GAP? And if it is, how can I do it? I know the basics of GAP.

(This is a follow-up to my question How to solve a quadratic equation over finite fields with GAP.. in which I asked for solutions to polynomial equations. I however need to say GAP what irreducible polynomial to take to construct the field.)

Answer 1

Basically you want to change coefficient between two bases. Your field has the basis $1,a,a^2,...$, GAP's field uses another basis, namely its own primitive element $b$. For example, for $p=2$ and polynomial $x^2+x-1$ and some (here randomly chosen) $c\in GF(7^2)$:

gap> p:=7;;x:=X(GF(p),"x");; pol:=x^2+x-1;;
gap> c:=Random(GF(7^2));
Z(7^2)^4

First calculate a basis for the field. We can for example calculate coefficients wrt this basis:

gap> b:=Basis(GF(p^2));
CanonicalBasis( GF(7^2) )
gap> BasisVectors(b);
[ Z(7)^0, Z(7^2) ]
gap> Coefficients(b,c);
[ Z(7)^3, Z(7)^2 ]
gap> List(last, Int);
[ 6, 2 ]

To get the base change, lets calculate $a$ and get coefficient vectors for $1,a,...$:

gap> a:=RootsOfUPol(GF(7^2),pol)[1]; # doesn't matter which root we take.
Z(7^2)^3
gap> abas:=[a^0,a];
[ Z(7)^0, Z(7^2)^3 ]
gap> mat:=List(abas,x->Coefficients(b,x));
[ [ Z(7)^0, 0*Z(7) ], [ Z(7)^4, Z(7)^5 ] ]
gap> Display(mat);
 1 .
 4 5

To express elements in terms of the $a$-basis we need the inverse matrix:

gap> inv:=mat^-1;Display(inv);
[ [ Z(7)^0, 0*Z(7) ], [ Z(7)^2, Z(7) ] ]
 1 .
 2 3

Now we use this inverse to convert the coeffiicients of $c$ wrt. GAP's basis to the $a$-basis. (Multiplication from the right, as GAP uses row vectors.)

gap> Coefficients(b,c)*inv;
[ Z(7), Z(7)^3 ]
gap> List(last,Int);
[ 3, 6 ]
gap> 3+6*a;
Z(7^2)^4

(The last 4 lines verify the calculation. Indeed $c=3+6*a$.)

If you wanted to display finite field elements prettily in your basis, the following hack function (using polynomials over the integers) would do so:

gap> avar:=X(Rationals,"a");
a

gap> abasrep:=function(x)
  return UnivariatePolynomial(Rationals,List(Coefficients(b,x)*inv,Int),avar);
end;

gap> List(Elements(GF(49)),x->abasrep(x));
[ 0, 1, 3, 2, 6, 4, 5, 3*a+2, 3*a+6, a, 6*a+3, 3*a+3, 6*a+1, 4*a+6, 2*a+6,
  2*a+4, 3*a, 4*a+2, 2*a+2, 4*a+3, 5*a+4, 6*a+4, 6*a+5, 2*a, 5*a+6, 6*a+6,
  5*a+2, a+5, 4*a+5, 4*a+1, 6*a, a+4, 4*a+4, a+6, 3*a+1, 5*a+1, 5*a+3, 4*a,
  3*a+5, 5*a+5, 3*a+4, 2*a+3, a+3, a+2, 5*a, 2*a+1, a+1, 2*a+5, 6*a+2 ]

and as the exaple shows you could even apply this function to lists of numbers.