1#############################################################################
2##
3##  This file is part of GAP, a system for computational discrete algebra.
4##  This file's authors include Werner Nickel, Martin Schönert.
5##
6##  Copyright of GAP belongs to its developers, whose names are too numerous
7##  to list here. Please refer to the COPYRIGHT file for details.
8##
9##  SPDX-License-Identifier: GPL-2.0-or-later
10##
11##  This file    contains  methods for  finite  fields.    Note that  we must
12##  distinguish finite fields and fields that  consist of `FFE's.  (The image
13##  of the natural embedding of the field  `GF(<q>)' into a field of rational
14##  functions is of  course a finite field  but  its elements are  not `FFE's
15##  since this would be a property given by their family.)
16##
17##  Special methods for `FFE's can be found in the file `ffe.gi'.
18##
19##  1. Miscellaneous Functions
20##  2. Groups of FFEs
21##  3. Bases of Finite Fields
22##  4. Automorphisms of Finite Fields
23##
24
25
26#############################################################################
27##
28##  1. Miscellaneous Functions
29##
30
31
32#############################################################################
33##
34#M  GeneratorsOfLeftModule( <F> ) . . . .  the vectors of the canonical basis
35##
36InstallMethod( GeneratorsOfLeftModule,
37    "for a finite field (return the vectors of the canonical basis)",
38    [ IsField and IsFinite ],
39    function( F )
40    local z;
41    z:= RootOfDefiningPolynomial( F );
42    return List( [ 0 .. Dimension( F ) - 1 ], i -> z^i );
43#T call of `UseBasis' ?
44    end );
45
46
47#############################################################################
48##
49#M  Random( <F> ) . . . . . . . . . . . .  random element from a finite field
50##
51##  We have special methods for finite prime fields and for fields with
52##  primitive root, for efficiency reasons.
53##  All other cases are handled by the vector space methods.
54##
55InstallMethodWithRandomSource( Random,
56    "for a random source and a finite prime field",
57    [ IsRandomSource, IsField and IsPrimeField and IsFinite ],
58    { rs, F } -> Random(rs,1,Size(F)) * One( F ) );
59
60InstallMethodWithRandomSource( Random,
61    "for a random source and a finite field with known primitive root",
62    [ IsRandomSource, IsField and IsFinite and HasPrimitiveRoot ],
63    function ( rs, F )
64    local   rnd;
65    rnd := Random( rs, 0, Size( F )-1 );
66    if rnd = 0  then
67      rnd := Zero( F );
68    else
69      rnd := PrimitiveRoot( F )^rnd;
70    fi;
71    return rnd;
72    end );
73
74
75#############################################################################
76##
77#M  Units( <F> )  . . . . . . . . . . . . . . . . . . . . via `PrimitiveRoot'
78##
79InstallMethod( Units,
80    "for a finite field",
81    [ IsField and IsFinite ],
82    function ( F )
83    local G;
84    G := GroupByGenerators( [ PrimitiveRoot( F ) ] );
85    if HasSize( F ) then
86      SetSize( G, Size( F )-1 );
87    fi;
88    return G;
89    end );
90
91
92#############################################################################
93##
94#M  \=( <F>, <G> ) . . . . . . . . . . . . . . . . . .  for two finite fields
95##
96##  Note that for two finite fields in the same family,
97##  it suffices to check the dimensions as vector spaces over the (common)
98##  prime field.
99##
100InstallMethod( \=,
101    "for two finite fields in the same family",
102    IsIdenticalObj,
103    [ IsField and IsFinite, IsField and IsFinite ],
104    function ( F, G )
105    return DegreeOverPrimeField( F ) = DegreeOverPrimeField( G );
106    end );
107
108
109#############################################################################
110##
111#M  IsSubset( <F>, <G> )  . . . . . . . . . . . . . . . for two finite fields
112##
113##  Note that for two finite fields in the same family,
114##  it suffices to check the dimensions as vector spaces over the (common)
115##  prime field.
116##
117InstallMethod( IsSubset,
118    "for two finite fields in the same family",
119    IsIdenticalObj,
120    [ IsField and IsFinite, IsField and IsFinite ],
121    function( F, G )
122    return DegreeOverPrimeField( F ) mod DegreeOverPrimeField( G ) = 0;
123    end );
124
125
126#############################################################################
127##
128#M  Subfields( <F> )  . . . . . . . . . . . . . . subfields of a finite field
129##
130InstallMethod( Subfields,
131    "for finite field of FFEs",
132    [ IsField and IsFFECollection ],
133    function( F )
134    local d, p;
135    d:= DegreeOverPrimeField( F );
136    p:= Characteristic( F );
137    return List( DivisorsInt( d ), n -> GF( p, n ) );
138    end );
139
140#############################################################################
141##
142#M  Subfields( <F> )  . . . . . . . . . . . . . . subfields of a finite field
143##
144InstallMethod( Subfields, "for finite fields that are not FFEs",
145    [ IsField and IsFinite ],
146function( F )
147local d, p,l,i,mp,fac,S;
148  d:= DegreeOverPrimeField( F );
149  p:= Characteristic( F );
150  l:=[];
151  for i in Filtered(DivisorsInt(d),x->x<d) do
152    mp:=MinimalPolynomial(GF(p),PrimitiveRoot(GF(p^i)));
153    mp:=Value(mp,X(F),One(F));
154    fac:=Factors(mp);
155    fac:=RootsOfUPol(fac[1])[1]; # one root
156    S:=FieldByGenerators([fac]);
157    SetDegreeOverPrimeField(S,i);
158    SetSize(S,p^i);
159    # hack, as there is no good print routine for subfields
160    SetName(S,Concatenation("Field([",String(fac),"])"));
161    Add(l,S);
162  od;
163  Add(l,F); # field itself -- save on expensive factorization
164  return l;
165end );
166
167
168#############################################################################
169##
170#M  PrimeField( <F> ) . . . . . . . . . . . . . . . . . .  for a finite field
171##
172InstallMethod( PrimeField,
173    "for finite field of FFEs",
174    [ IsField and IsFFECollection ],
175    F -> GF( Characteristic( F ) ) );
176
177
178#############################################################################
179##
180#M  MinimalPolynomial( <F>, <z>, <inum> )
181##
182InstallMethod( MinimalPolynomial,
183    "finite field, finite field element, and indet. number",
184    IsCollsElmsX,
185    [ IsField and IsFinite, IsScalar, IsPosInt ],
186function( F, z, inum )
187    local   df,  dz,  q,  dd,  pol,  deg,  con,  i;
188
189    # get the field in which <z> lies
190    df := DegreeOverPrimeField(F);
191    dz := DegreeOverPrimeField(DefaultField(z));
192    q  := Size(F);
193    dd := LcmInt(df,dz) / df;
194
195    # compute the minimal polynomial simply by multiplying $x-cnj$
196    pol := [ One(F) ];
197    deg := 0;
198    for con  in Set( List( [ 0 .. dd-1 ], x -> z^(q^x) ) )  do
199        pol[deg+2] := pol[deg+1];
200        for i  in [ deg+1, deg .. 2 ]  do
201            pol[i] := pol[i-1] -  con*pol[i];
202        od;
203        pol[1] := -con*pol[1];
204        deg := deg + 1;
205    od;
206
207    # return the coefficients list of the minimal polynomial
208    return UnivariatePolynomial( F, pol, inum );
209end );
210
211
212#############################################################################
213##
214##  2. Groups of FFEs
215##
216
217
218#############################################################################
219##
220#M  IsHandledByNiceMonomorphism( <G> )  . . . . . . `true' for groups of FFEs
221##
222InstallTrueMethod( IsHandledByNiceMonomorphism,
223    IsGroup and IsFFECollection );
224
225
226#############################################################################
227##
228#M  IsCyclic( <G> ) . . . . . . . . . . . . . . . . groups of FFEs are cyclic
229##
230InstallTrueMethod( IsCyclic, IsGroup and IsFFECollection );
231
232
233#############################################################################
234##
235#M  <elm> in <G>  . . . . . . . . . . . . . . . . . . . . via `PrimitiveRoot'
236##
237InstallMethod( \in,
238    "for groups of FFE",
239    IsElmsColls,
240    [ IsFFE, IsGroup and IsFFECollection ],
241    function( elm, G )
242    local F;
243
244    F:= Field( Concatenation( GeneratorsOfGroup( G ), [ One( G ) ] ) );
245    return     elm in F and not IsZero( elm )
246           and LogFFE( elm, PrimitiveRoot( F ) ) mod
247               ( ( Size( F ) - 1 ) / Size( G ) ) = 0;
248    end );
249
250
251#############################################################################
252##
253#M  Size( <G> ) . . . . . . . . . . . . . . . . . . . . . via `PrimitiveRoot'
254##
255InstallMethod( Size,
256    "for groups of FFE",
257    [ IsGroup and IsFFECollection ],
258    function( G )
259    local   gens, F, z, k;
260
261    if IsTrivial( G )  then
262        return 1;
263    fi;
264
265    gens := GeneratorsOfGroup( G );
266    F := Field( gens );
267    z := PrimitiveRoot( F );
268    k := Gcd( Integers, List( gens, g -> LogFFE(g, z) ) );
269    return ( Size( F ) - 1 ) /  GcdInt(k, ( Size( F ) - 1 ));
270end );
271
272
273#############################################################################
274##
275#M  AbelianInvariants( <G> ) . . . . . . . . . . . . . .  via `PrimitiveRoot'
276##
277InstallMethod( AbelianInvariants,
278    "for groups of FFE",
279    [ IsGroup and IsFFECollection ],
280    G -> AbelianInvariantsOfList( [Size( G )] ) );
281
282#############################################################################
283##
284#M  CanEasilyComputeWithIndependentGensAbelianGroup( <G> )
285##
286InstallTrueMethod(CanEasilyComputeWithIndependentGensAbelianGroup,
287    IsGroup and IsFFECollection);
288
289#############################################################################
290##
291#M  IndependentGeneratorsOfAbelianGroup( <G> ) . . . . .  via `PrimitiveRoot'
292##
293InstallMethod( IndependentGeneratorsOfAbelianGroup,
294    "for groups of FFE",
295    [ IsGroup and IsFFECollection ],
296    function( G )
297    local   F, g, base, ord, o, cf, j;
298
299    if IsTrivial( G )  then
300        return [];
301    fi;
302
303    F := Field( GeneratorsOfGroup( G ) );
304    g := PrimitiveRoot( F ) ^ ( ( Size( F ) - 1 ) / Size( G ) );
305    base := [];
306    ord := [];
307    o := Order( g );
308    cf:=Collected( Factors( o ) );
309    for j in cf do
310        j := j[1]^j[2];
311        Add( base, g^(o/j) );
312        Add( ord, j );
313    od;
314    SortParallel(ord,base);
315    return base;
316end );
317
318#############################################################################
319##
320#M  IndependentGeneratorExponents( <G> ) . . . . . . . .  via `PrimitiveRoot'
321##
322InstallMethod( IndependentGeneratorExponents,
323    "for groups of FFE",
324    IsCollsElms,
325    [ IsGroup and IsFFECollection, IsFFE ],
326    function( G, elm )
327    local   F, z, gens, j, exps;
328
329    if IsTrivial( G )  then
330        return [];
331    fi;
332
333    F := Field( GeneratorsOfGroup( G ) );
334    z := PrimitiveRoot( F );
335    gens := IndependentGeneratorsOfAbelianGroup( G );
336
337    # We need to compute LogFFE for every element of gens, which is
338    # in general quite expensive. But if gens was computed by our
339    # IndependentGeneratorsOfAbelianGroup method, then we actually
340    # know the LogFFE value. Since verifying this is cheap, try that
341    # first before resorting to LogFFE.
342    exps := List( gens, g -> ( Size(F) - 1 ) / Order( g ) );
343
344    if ForAny( [ 1 .. Length(exps) ], i -> gens[i] <> z^exps[i] ) then
345        # We have to do it the hard way...
346        exps := List( gens, g -> LogFFE( g, z ) );
347    fi;
348
349    j := LogFFE( elm, z );
350    exps := List( [1..Length(exps)], i -> ( j / exps[i] ) mod Order( gens[i] ) );
351
352    Assert( 0, elm = Product( [1..Length(exps)], i -> gens[i]^exps[i]) );
353    return exps;
354end );
355
356
357#############################################################################
358##
359##  3. Bases of Finite Fields
360##
361##  *Note*:  Bases of *subspaces* of fields which are themselves not fields
362##  are handled by the mechanism of nice bases (see `field.gi').
363##
364
365
366#############################################################################
367##
368#R  IsBasisFiniteFieldRep( <F> )
369##
370##  Bases of finite fields in the representation `IsBasisFiniteFieldRep'
371##  are dealt with as follows.
372##
373##  Coefficients w.r.t.~a basis $B = (b_0, b_1, \ldots, b_d)$ of the field
374##  extension $GF(q^{d+1})$ over $GF(q)$ can be computed as follows.
375##  $x \in GF(q^{d+1})$ is of the form $x = \sum_{i=0}^d a_i b_i$,
376##  with $a_i \in GF(q)$, if and only if for $0 \leq k \leq d$ the equation
377##  $x^{q^k} = \sum_{i=0}^d a_i b_i^{q^k}$ holds.
378##  Thus we have the matrix equation
379##  $$
380##  [ x^{q^k} ]_{k=0}^d = [ a_i ]_{i=0}^d [ b_i^{q^k} ]_{i,k=0}^d ,
381##  $$
382##  from which the coefficients $a_i$ can be computed.
383##  The inverse of the matrix $[ b_i^{q^k} ]_{i,k=0}^d$ is stored in the
384##  basis as value of the component `inverseBase'.
385##
386DeclareRepresentation( "IsBasisFiniteFieldRep",
387    IsAttributeStoringRep,
388    [ "inverseBase", "d", "q" ] );
389
390InstallTrueMethod( IsFinite, IsBasis and IsBasisFiniteFieldRep );
391
392
393#############################################################################
394##
395#M  Basis( <F> )
396##
397##  We know a canonical basis for finite fields.
398##
399InstallMethod( Basis,
400    "for a finite field (delegate to `CanonicalBasis')",
401    [ IsField and IsFinite ], CANONICAL_BASIS_FLAGS,
402    CanonicalBasis );
403
404
405#############################################################################
406##
407#M  Basis( <F>, <gens> )
408#M  BasisNC( <F>, <gens> )
409##
410InstallMethod( Basis,
411    "for a finite field, and a hom. list",
412    IsIdenticalObj,
413    [ IsField and IsFinite, IsFFECollection and IsList ],
414    function( F, gens )
415
416    local B,     # the basis, result
417          q,     # size of the subfield
418          d,     # dimension of the extension
419          mat,
420          b,b1,
421          cnjs,
422          k;
423
424    # Set up the basis object.
425    B:= Objectify( NewType( FamilyObj( gens ),
426                                IsFiniteBasisDefault
427                            and IsBasisFiniteFieldRep ),
428                   rec() );
429    SetUnderlyingLeftModule( B, F );
430    SetBasisVectors( B, gens );
431
432    # Get the size `q' of the subfield and the dimension `d'
433    # of the extension with respect to the subfield.
434    q:= Size( LeftActingDomain( F ) );
435    d:= Dimension( F );
436
437    # Test that the basis vectors really define the
438    # (unique) finite field extension of degree `d'.
439    if d <> Length( gens ) then
440      return fail;
441    fi;
442
443    # Build the matrix `M[i][k] = vectors[i]^(q^k)'.
444    mat:= [];
445    for b in gens do
446        cnjs := [];
447        b1 := b;
448        cnjs := [b];
449        for k in [ 1 .. d-1 ] do
450            b1 := b1^q;
451            Add( cnjs, b1 );
452        od;
453        Add( mat, cnjs );
454    od;
455
456    # We have a basis if and only if `mat' is invertible.
457    if Length(mat) > 0 then
458        mat:= Inverse( mat );
459        if mat = fail then
460            return fail;
461        fi;
462    else
463        mat := Immutable(mat);
464    fi;
465
466    # Add the coefficients information.
467    B!.inverseBase:= mat;
468    B!.d:= d;
469    B!.q:= q;
470
471    # Return the basis.
472    return B;
473    end );
474
475InstallMethod( BasisNC,
476    "for a finite field, and a hom. list",
477    IsIdenticalObj,
478    [ IsField and IsFinite, IsHomogeneousList ], 10,
479    function( F, gens )
480
481    local B,     # the basis, result
482          q,     # size of the subfield
483          d,     # dimension of the extension
484          mat,
485          b,b1,
486          cnjs,
487          k;
488
489    # Set up the basis object.
490    B:= Objectify( NewType( FamilyObj( gens ),
491                                IsFiniteBasisDefault
492                            and IsBasisFiniteFieldRep ),
493                   rec() );
494    SetUnderlyingLeftModule( B, F );
495    SetBasisVectors( B, gens );
496
497    # Get the size `q' of the subfield and the dimension `d'
498    # of the extension with respect to the subfield.
499    q:= Size( LeftActingDomain( F ) );
500    d:= Dimension( F );
501
502    # Build the matrix `M[i][k] = vectors[i]^(q^k)'.
503    mat:= [];
504    for b in gens do
505        cnjs := [b];
506        b1 := b;
507        for k in [ 1 .. d-1 ] do
508            b1 := b1^q;
509            Add( cnjs, b1 );
510        od;
511        Add( mat, cnjs );
512    od;
513
514    # Add the coefficients information.
515    if Length(mat) > 0 then
516        B!.inverseBase:= Inverse( mat );
517    else
518        B!.inverseBase:= Immutable(mat);
519    fi;
520    B!.d:= d;
521    B!.q:= q;
522
523    # Return the basis.
524    return B;
525    end );
526
527
528#############################################################################
529##
530#M  Coefficients( <B>, <z> )  . . . . . . . . . . for basis of a finite field
531##
532InstallMethod( Coefficients,
533    "for a basis of a finite field, and a scalar",
534    IsCollsElms,
535    [ IsBasis and IsBasisFiniteFieldRep, IsScalar ],
536    function ( B, z )
537    local   q, d, k, zz;
538
539    if   not z in UnderlyingLeftModule( B ) then
540      return fail;
541    fi;
542
543    # Get the size `q' of the subfield and the degree `d' of the extension
544    # with respect to the subfield.
545    q := B!.q;
546    d := B!.d;
547
548    # Compute the vector of conjugates of `z'.
549    zz := [];
550    for k  in [0..d-1]  do
551        Add( zz, z^(q^k) );
552    od;
553
554    # The `inverseBase' component of the basis defines the base change
555    # to the normal basis.
556    return zz * B!.inverseBase;
557    end );
558
559
560#############################################################################
561##
562#M  LinearCombination( <B>, <coeffs> )
563##
564InstallMethod( LinearCombination,
565    "for a basis of a finite field, and a hom. list",
566    IsIdenticalObj,
567    [ IsBasis and IsBasisFiniteFieldRep, IsHomogeneousList ],
568        function ( B, coeffs )
569    if Length(coeffs) = 0 then
570        TryNextMethod();
571    fi;
572    return coeffs * BasisVectors( B );
573#T This calls PROD_LIST_LIST_DEFAULT
574#T if both lists are known to be small,
575#T and PROD_LIST_LIST_TRY otherwise!
576#T Is this method necessary at all??
577    end );
578
579
580#############################################################################
581##
582#M  CanonicalBasis( <F> )
583##
584##  The canonical basis of the finite field with $p^n$ elements, viewed over
585##  its subfield with $p^d$ elements, consists of the vectors `<z> ^ <i>',
586##  $0 \leq i \< n/d$, where <z> is the primitive root of <F>.
587##
588InstallMethod( CanonicalBasis,
589    "for a finite field",
590    [ IsField and IsFinite ],
591    function( F )
592    local z,         # primitive root
593          B;         # basis record, result
594
595    z:= RootOfDefiningPolynomial( F );
596    B:= BasisNC( F, List( [ 0 .. Dimension( F ) - 1 ], i -> z ^ i ) );
597    SetIsCanonicalBasis( B, true );
598
599    # Return the basis object.
600    return B;
601    end );
602
603
604#############################################################################
605##
606#M  NormalBase( <F>, <elm> )
607##
608##  For finite fields just search.
609##
610InstallMethod( NormalBase,
611"for a finite field and scalar",
612    [ IsField and IsFinite, IsScalar ],
613function(F, b)
614    local q, d, z, l, bas, i;
615    if b=0*b then
616        b := One(F);
617    fi;
618    q := Size(LeftActingDomain(F));
619    d := Dimension(F);
620    z := PrimitiveRoot(F);
621    repeat
622        l := [b];
623        for i in [1..d-1] do
624          Add(l, l[i]^q);
625        od;
626        bas := Basis(F, l);
627        b := b*z;
628    until bas <> fail;
629    return l;
630end);
631
632
633#############################################################################
634##
635##  4. Automorphisms of Finite Fields
636##
637
638
639#############################################################################
640##
641#R  IsFrobeniusAutomorphism( <obj> )  . test if an object is a Frobenius aut.
642##
643DeclareRepresentation( "IsFrobeniusAutomorphism",
644        IsFieldHomomorphism
645    and IsMapping
646    and IsAttributeStoringRep,
647    [ "power" ] );
648
649
650#############################################################################
651##
652#F  FrobeniusAutomorphism(<F>)  . .  Frobenius automorphism of a finite field
653##
654BindGlobal( "FrobeniusAutomorphismI", function ( F, i )
655
656    local Fam, frob;
657
658    # Catch the bad case.
659    if Size( F ) = 2 then
660      i:= 1;
661    else
662      i:= i mod ( Size( F ) - 1 );
663    fi;
664
665    if i = 1 then
666      return IdentityMapping( F );
667    fi;
668
669    Fam:= ElementsFamily( FamilyObj( F ) );
670
671    # make the mapping object
672    frob:= Objectify( TypeOfDefaultGeneralMapping( F, F,
673                              IsFrobeniusAutomorphism
674                          and IsSPGeneralMapping
675                          and IsRingWithOneHomomorphism
676                          and IsBijective ),
677                      rec() );
678
679    frob!.power := i;
680
681    return frob;
682end );
683
684InstallMethod( FrobeniusAutomorphism,
685    "for a field",
686    [ IsField ],
687    function ( F )
688
689    # check the arguments
690    if not IsPosRat( Characteristic( F ) ) then
691        Error( "<F> must be a field of nonzero characteristic" );
692    fi;
693
694    # return the automorphism
695    return FrobeniusAutomorphismI( F, Characteristic( F ) );
696end );
697
698
699#############################################################################
700##
701#M  \=( <frob1>, <frob2> )
702#M  \=( <id>, <frob> )
703#M  \=( <frob>, <id> )
704##
705InstallMethod( \=,
706    "for two Frobenius automorphisms",
707    IsIdenticalObj,
708    [ IsFrobeniusAutomorphism, IsFrobeniusAutomorphism ],
709    function( aut1, aut2 )
710    return Source( aut1 ) = Source( aut2 ) and aut1!.power  = aut2!.power;
711    end );
712
713InstallMethod( \=,
714    "for identity mapping and Frobenius automorphism",
715    IsIdenticalObj,
716    [ IsMapping and IsOne, IsFrobeniusAutomorphism ],
717    function( id, aut )
718    return Source( id ) = Source( aut ) and aut!.power = 1;
719    end );
720
721InstallMethod( \=,
722    "for Frobenius automorphism and identity mapping",
723    IsIdenticalObj,
724    [ IsFrobeniusAutomorphism, IsMapping and IsOne ],
725    function( aut, id )
726    return Source( id ) = Source( aut ) and aut!.power = 1;
727    end );
728
729InstallMethod( ImageElm,
730    "for Frobenius automorphism and source element",
731    FamSourceEqFamElm,
732    [ IsFrobeniusAutomorphism, IsObject ],
733    function( aut, elm )
734    return elm ^ aut!.power;
735    end );
736
737InstallMethod( ImagesElm,
738    "for Frobenius automorphism and source element",
739    FamSourceEqFamElm,
740    [ IsFrobeniusAutomorphism, IsObject ],
741    function( aut, elm )
742    return [ elm ^ aut!.power ];
743    end );
744
745InstallMethod( ImagesSet,
746    "for Frobenius automorphism and field contained in the source",
747    CollFamSourceEqFamElms,
748    [ IsFrobeniusAutomorphism, IsField ],
749    function( aut, elms )
750    return elms;
751    end );
752
753InstallMethod( ImagesRepresentative,
754    "for Frobenius automorphism and source element",
755    FamSourceEqFamElm,
756    [ IsFrobeniusAutomorphism, IsObject ],
757    function( aut, elm )
758    return elm ^ aut!.power;
759    end );
760
761InstallMethod( CompositionMapping2,
762    "for two Frobenius automorphisms",
763    IsIdenticalObj,
764    [ IsFrobeniusAutomorphism, IsFrobeniusAutomorphism ],
765    function( aut1, aut2 )
766    if Characteristic( Source( aut1 ) )
767       = Characteristic( Source( aut2 ) ) then
768      return FrobeniusAutomorphismI( Source( aut1 ),
769                                     aut1!.power * aut2!.power );
770    else
771      Error( "Frobenius automorphisms of different characteristics" );
772    fi;
773    end );
774
775InstallMethod( InverseGeneralMapping,
776    "for a Frobenius automorphism",
777    [ IsFrobeniusAutomorphism ],
778    aut -> FrobeniusAutomorphismI( Source( aut ),
779                                   Size( Source( aut ) ) / aut!.power ) );
780
781InstallMethod( \^,
782    "for a Frobenius automorphism, and an integer",
783    [ IsFrobeniusAutomorphism, IsInt ],
784    function ( aut, i )
785    return FrobeniusAutomorphismI( Source( aut ),
786                   PowerModInt( aut!.power, i, Size( Source( aut ) ) - 1 ) );
787    end );
788
789InstallMethod( \<,
790    "for an identity mapping, and a Frobenius automorphism",
791    IsIdenticalObj,
792    [ IsMapping and IsOne, IsFrobeniusAutomorphism ],
793    function ( id, aut )
794    local source1, # source of `id'
795          source2, # source of `aut'
796          p,       # characteristic
797          root,    # primitive root of source
798          size,    # size of source
799          d,       # degree
800          gen;     # generator of cyclic group of subfield
801
802    source1:= Source( id );
803    source2:= Source( aut );
804    if source1 <> source2 then
805      return source1 < source2;
806    elif    PrimitiveRoot( source1 )
807         <> PrimitiveRoot( source2 ) then
808      return   PrimitiveRoot( source1 )
809             < PrimitiveRoot( source2 );
810#T o.k.?
811    else
812        p := Characteristic( source1 );
813        root:= PrimitiveRoot( source1 );
814        size:= Size( source1 );
815        for d  in DivisorsInt( LogInt( size, p ) )  do
816            gen:= root^( ( size - 1 ) / ( p^d - 1 ) );
817            if gen <> gen ^ aut!.power  then
818                return gen < gen ^ aut!.power;
819            fi;
820        od;
821        return false;
822    fi;
823    end );
824
825InstallMethod( \<,
826    "for a Frobenius automorphism, and an identity mapping",
827    IsIdenticalObj,
828    [ IsFrobeniusAutomorphism, IsMapping and IsOne ],
829    function ( aut, id )
830    local source1, # source of `aut'
831          source2, # source of `id'
832          p,       # characteristic
833          root,    # primitive root of source
834          size,    # size of source
835          d,       # degree
836          gen;     # generator of cyclic group of subfield
837
838    source1:= Source( aut );
839    source2:= Source( id );
840    if source1 <> source2 then
841      return source1 < source2;
842    elif    PrimitiveRoot( source1 )
843         <> PrimitiveRoot( source2 ) then
844      return   PrimitiveRoot( source1 )
845             < PrimitiveRoot( source2 );
846#T o.k.?
847    else
848        p := Characteristic( source1 );
849        root:= PrimitiveRoot( source1 );
850        size:= Size( source1 );
851        for d  in DivisorsInt( LogInt( size, p ) )  do
852            gen:= root^( ( size - 1 ) / ( p^d - 1 ) );
853            if gen ^ aut!.power <> gen then
854                return gen ^ aut!.power < gen;
855            fi;
856        od;
857        return false;
858    fi;
859    end );
860
861InstallMethod( \<,
862    "for two Frobenius automorphisms",
863    IsIdenticalObj,
864    [ IsFrobeniusAutomorphism, IsFrobeniusAutomorphism ],
865    function ( aut1, aut2 )
866    local source1, # source of `aut1'
867          source2, # source of `aut2'
868          p,       # characteristic
869          root,    # primitive root of source
870          size,    # size of source
871          d,       # degree
872          gen;     # generator of cyclic group of subfield
873
874    source1:= Source( aut1 );
875    source2:= Source( aut2 );
876    if source1 <> source2 then
877      return source1 < source2;
878    elif    PrimitiveRoot( source1 )
879         <> PrimitiveRoot( source2 ) then
880      return   PrimitiveRoot( source1 )
881             < PrimitiveRoot( source2 );
882#T o.k.?
883    else
884        p := Characteristic( source1 );
885        root:= PrimitiveRoot( source1 );
886        size:= Size( source1 );
887        for d  in DivisorsInt( LogInt( size, p ) )  do
888            gen:= root^( ( size - 1 ) / ( p^d - 1 ) );
889            if gen ^ aut1!.power <> gen ^ aut2!.power  then
890                return gen ^ aut1!.power < gen ^ aut2!.power;
891            fi;
892        od;
893        return false;
894    fi;
895    end );
896
897InstallMethod( PrintObj,
898    "for a Frobenius automorphism",
899    [ IsFrobeniusAutomorphism ],
900    function ( aut )
901    if aut!.power = Characteristic( Source( aut ) ) then
902        Print( "FrobeniusAutomorphism( ", Source( aut ), " )" );
903    else
904        Print( "FrobeniusAutomorphism( ", Source( aut ), " )^",
905               LogInt( aut!.power, Characteristic( Source( aut ) ) ) );
906    fi;
907    end );
908
909
910#############################################################################
911##
912#M  GaloisGroup( <F> )  . . . . . . . . . . .  Galois group of a finite field
913##
914InstallMethod( GaloisGroup,
915    "for a finite field",
916    [ IsField and IsFinite ],
917    F -> GroupByGenerators(
918            [ FrobeniusAutomorphismI( F, Size( LeftActingDomain(F) ) ) ] ) );
919