[GAP Forum] Normal basis of a finite field

[Frank Luebeck]

On Thu, 21 Oct 2004, Yannis Michos wrote:

> Dear  GAP users,
> How do I  find a normal  basis of a finite  field K?
> Suppose for example that K := GF(16).  I use the command NormalBase(K) I saw
> in the  manual but  there is  a problem.  It seems  I have  to use  the form
> NormalBase(K, elm) but should the element elm be?

Dear GAP-forum, dear Yannis Michos,

Yes there is a problem: So far, nobody implemented a method for computing
a normal base of a finite field. After reading the code below into your
GAP session  commands like

NormalBase( GF(16) );
NormalBase( GF( GF(4), 2 ) );

will work.

A method for this will be included in future updates of GAP.

With best regards,

   Frank Lübeck


///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,  ///
\\\                    52062 Aachen, Germany                          \\\
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De                        ///
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/           \\\


InstallMethod( NormalBase,
"for a finite field and scalar",
    [ IsField and IsFinite, IsScalar ],
function(F, b)
    local q, d, z, l, bas, i;
    if b=0*b then
        b := One(F);
    fi;
    q := Size(LeftActingDomain(F));
    d := Dimension(F);
    z := PrimitiveRoot(F);
    repeat
        l := [b];
        for i in [1..d-1] do
          Add(l, l[i]^q);
        od;
        bas := Basis(F, l);
        b := b*z;
    until bas <> fail;
    return l;
end);