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