[GAP Forum] Re: Normal basis of a finite field

[Mowsey]

I think GAP does not currently provide a function to compute a
normal base of a finite field. Luckily for the finite fields that
GAP supports it is fairly quick just to find one yourself.  There are
some theoretical results on how quickly this works, but since GF(p^n)
and Z(p^n) require p^n < 2^17 or so, I can't easily access fields
large enough to make this silly search not obviously fine:

NormalBase_FiniteFieldSimpleSearch:=function(p,n)
        local i;
        i:=1;
        while( n > Dimension(VectorSpace(GF(p),Conjugates(Z(p^n)^i))) )
        do i:=i+1; od;
        return Conjugates(Z(p^n)^i);
end;

Z(p^n) is a root of the polynomial ConwayPolynomial(p,n) and is a
primitive element of the corresponding finite field of size p^n.

The only fields this applies to are the fields whose order is
in the list Q:=[
 4, 8, 9, 16, 25, 27, 32, 49, 64, 81, 121, 125, 128, 169,
 243, 256, 289, 343, 361, 512, 529, 625, 729, 841, 961, 1024,
 1331, 1369, 1681, 1849, 2048, 2187, 2197, 2209, 2401, 2809,
 3125, 3481, 3721, 4096, 4489, 4913, 5041, 5329, 6241, 6561,
 6859, 6889, 7921, 8192, 9409, 10201, 10609, 11449, 11881,
 12167, 12769, 14641, 15625, 16129, 16384, 16807, 17161, 18769,
 19321, 19683, 22201, 22801, 24389, 24649, 26569, 27889, 28561,
 29791, 29929, 32041, 32761, 32768, 36481, 37249, 38809, 39601,
 44521, 49729, 50653, 51529, 52441, 54289, 57121, 58081, 59049,
 63001, 65536];

And the command
for q in Q do
        p:=SmallestRootInt(q); n:=LogInt(q,p);
        NormalBase_FiniteFieldSimpleSearch(p,n);
od;

runs in a few seconds on a cheap personal computer.