[GAP Forum] Finite field defined with an irreducible polynomial

[Thomas Breuer]

Dear GAP Forum,

Anvita (<anvita21 at gmail.com>) wrote:

> When a finite field is defined using an irreducible polynomial, there seems
> to be a problem
> finding the coefficients of the field's elements in the natural power bases.
> For example:
> 
> ----------------------------------------
> gap> x:=Indeterminate(GF(5),"x");
> x
> gap> pol:=x^7+x^4+x^2-x+Z(5);
> x^7+x^4+x^2-x+Z(5)
> gap> F:=GF(GF(5),pol);
> <field of size 78125>
> gap> a:=RootOfDefiningPolynomial(F);
> (a)
> gap> t:=a^32;
> (Z(5)^2+Z(5)*a^2+Z(5)*a^3+Z(5)^2*a^5+a^6)
> -----------------------------------------
> 
> Even though "t" is displayed as a polynomial in "a", I do not know
> how to get hold of the corresponding coefficients, because the field "F"
> as a vector space does not have a basis:
> 
> --------------------------------------------------------------------------------
> gap>IsVectorSpace(F);
> true
> gap> b:=List([0..6],i->a^i);
> [ !Z(5)^0, (a), (a^2), (a^3), (a^4), (a^5), (a^6) ]
> gap> Basis(F,b);
> Error, no method found! For debugging hints type ?Recovery from
> [...]
> 
> Is there any way around this problem?

This problem will be fixed in the next version of GAP.

Erik Postma has already proposed a workaround, which works well,
but clearly it should be possible to compute a basis for the finite field
itself.
For the moment, reading the following code into the GAP session
will add the missing functionality.

  InstallMethod( CanonicalBasis,
    "for a finite field",
    [ IsField and IsFinite ],
    function( F )
    local z, B;

    z:= RootOfDefiningPolynomial( F );
    B:= BasisNC( F, List( [ 0 .. Dimension( F ) - 1 ], i -> z ^ i ) );
    SetIsCanonicalBasis( B, true );

    return B;
    end );

(To those who are interested:
If one asks for a basis of a finite field then `CanonicalBasis' is used,
and the currently available method for this operation wants to use
the attribute `PrimitiveRoot'.
This is fine if a primitive root of the field is known, and this is the case
if the field was constructed using a primitive polynomial,
for example by the ``standard'' call `GF(q)'.
If no primitive root of the field is known then GAP runs into the reported
error, and indeed it does not make sense to look for a primitive root.
In order to generalize the current `CanonicalBasis' method to other defining
polynomials, it is sufficient to use `RootOfDefiningPolynomial' instead of
`PrimitiveRoot'.
In fact there are only few situations where one really wants to use
`PrimitiveRoot'.)

Thanks for reporting this problem,
and sorry for the inconveniences.

All the best,
Thomas Breuer