Quelle StandardFF.gi Sprache: unbekannt

#############################################################################
##
#A StandardFF.gi Frank Lübeck
##
## The files StandardFF.g{i,d} contain code to compute standard models of
## finite fields. Fields are returned as field towers with prime degree
## indices, and as single extensions over the prime field.
##

# args: p, r, k
# Let f = X^r + g(X) our standard irreducible polynomial for the
# degree r extension over the field FF(p,r^(k-1)). This function
# returns the Steinitz number of the polynomial g(X).
InstallGlobalFunction(SteinitzNumberForPrimeDegree, function(p, r, k)
 local Fp, stpd, stpdr, q, F, o, i, nr, x, a, l;
 Fp := StandardFiniteField(p, 1);
 if not IsBound(Fp!.SteinitzPrimeDeg) then
 Fp!.SteinitzPrimeDeg := [];
 fi;
 stpd := Fp!.SteinitzPrimeDeg;
 if not IsBound(stpd[r]) then
 stpd[r] := [];
 fi;
 stpdr := stpd[r];
 if not IsBound(stpdr[k]) then
 if p = r then
 # Artin-Schreier case
 # Xk^p - Xk - \prod_{1..k-1} x_i^(p-1)
 # for q = p^(p^(k-1)) this yields (p-1)*(q + q/p)
 q := p^(p^(k-1));
 stpdr[k] := (p-1)*(q+q/p);
 elif r = 2 and p mod 4 = 3 then
 # special case for k = 1, 2
 if k = 1 then
 # X^2 + 1
 stpdr[k] := 1;
 elif k = 2 then
 # find a non-square
 F := StandardFiniteField(p, 2);
 o := One(F);
 i := 1;
 nr := StandardAffineShift(p^2, i);
 x := ElementSteinitzNumber(F, nr);
 while nr = 0 or x^((p^2-1)/2) = o do
 i := i+1;
 nr := StandardAffineShift(p^2, i);
 x := ElementSteinitzNumber(F, nr);
 od;
 # X^2 - x
 stpdr[k] := SteinitzNumber(-x);
 else
 # Xk - x{k-1}
 stpdr[k] := (p-1)*p^(2^(k-2));
 fi;
 elif (p-1) mod r = 0 then
 if k = 1 then
 # find a non r-th power
 i := 1;
 nr := StandardAffineShift(p, i);
 while nr = 0 or PowerMod(nr, (p-1)/r, p) = 1 do
 i := i+1;
 nr := StandardAffineShift(p, i);
 od;
 # X^r - nr
 stpdr[k] := p - nr;
 else
 # Xk^r - x{k-1}
 stpdr[k] := (p-1)*p^(r^(k-2));
 fi;
 else
 # in general we use pseudo random polynomials
 F := StandardFiniteField(p, r^(k-1));
 if k = 1 then
 # new generator will have norm 1
 a := -One(F);
 else
 # new generator will have previous one as norm
 a := -PrimitiveElement(F);
 fi;
 l := StandardIrreducibleCoeffList(F, r, a);
 Remove(l);
 while IsZero(l[Length(l)]) do
 Remove(l);
 od;
 stpdr[k] := ValuePol(List(l, SteinitzNumber), Size(F));
 fi;
 fi;
 return stpdr[k];
end);
# a version that tries to call external program using NTL
InstallGlobalFunction(SteinitzNumberForPrimeDegreeNTL, function(p, r, k)
 local Fp, stpd, stpdr, d, prg, inp, res;

 # for cache same as above
 Fp := StandardFiniteField(p, 1);
 if not IsBound(Fp!.SteinitzPrimeDeg) then
 Fp!.SteinitzPrimeDeg := [];
 fi;
 stpd := Fp!.SteinitzPrimeDeg;
 if not IsBound(stpd[r]) then
 stpd[r] := [];
 fi;
 stpdr := stpd[r];
 if not IsBound(stpdr[k]) then
 d := DirectoriesPackageLibrary("StandardFF","ntl");
 # currently we only have standalone programs for k = 1 and p < 2^50
 if k = 1 then
 if p = 2 then
 if r <> p and (p-1) mod r <> 0 then
 prg := Filename(d, "findstdirrGF2");
 if prg <> fail then
 inp := String(r);
 res := IO_PipeThrough(prg,[],inp);
 stpdr[k] := Int(Filtered(res, IsDigitChar));
 fi;
 fi;
 elif p < 2^50 then
 if r <> p and (p-1) mod r <> 0 then
 prg := Filename(d, "findstdirrGFp");
 if prg <> fail then
 inp := Concatenation(String(p), "\n", String(r));
 res := IO_PipeThrough(prg,[],inp);
 stpdr[k] := Int(Filtered(res, IsDigitChar));
 fi;
 fi;
 fi;
 fi;
 if not IsBound(stpdr[k]) then
 # use the GAP function
 SteinitzNumberForPrimeDegree(p, r, k);
 fi;
 fi;
 return stpdr[k];
end);

# for displaying the corresponding polynomial
InstallGlobalFunction(StandardPrimeDegreePolynomial, function(p, r, k)
 local st, qq, K, c, v;
 st := SteinitzNumberForPrimeDegree(p, r, k);
 qq := p^(r^(k-1));
 K := FF(p, r^(k-1));
 c := CoefficientsQadic(st, qq);
 while Length(c) < r do
 Add(c, 0);
 od;
 Add(c, 1);
 c := List(c, i-> AsPolynomial(ElementSteinitzNumber(K, i)));
 v := Indeterminate(FF(p,1), Concatenation("x",String(r),"_",String(k)));
 return ValuePol(c, v);
end);

# args: K, deg, lcoeffs, b
# Let f = poly(lcoeffs) + X^deg be irreducible in K[X].
# Return K[X] / f with primitve element bX mod f, where b in K
# such that bX mod f is a generator over the prime field.
# We assume that K = F[Y] / g and K knows powers of the primitive element
# Y mod g in its tower basis.
# The returned fields also stores the powers of bX mod f in its tower
# basis.
# (The semiechelon code is similar to 'Matrix_OrderPolynomialInner'.)
InstallGlobalFunction(_ExtensionWithTowerBasis, function(K, deg, lcoeffs, b)
 local dK, zK, zKl, co, d, F, zero, one, pK, vec, vecs, pols,
 zeroes, pmat, v, w, p, piv, x, c, vnam, var, ivar, Kp, fam, i, j;
 dK := DegreeOverPrimeField(K);
 d := dK * deg;
 F := LeftActingDomain(K);
 # shortcut for prime degree over prime field
 if dK = 1 then
 p := ShallowCopy(lcoeffs);
 while Length(p) < deg do
 Add(p, 0*p[1]);
 od;
 Add(p, One(p[1]));
 MakeImmutable(p);
 pmat := IdentityMat(deg, F);
 else
 zK := Zero(K);
 zero := Zero(F);
 one := One(F);
 pK := PrimitivePowersInTowerBasis(K);
 co := function(x)
 local res;
 if dK = 1 then
 res := [x];
 else
 res := x![1];
 if not IsList(res) then
 res := zero * [1..dK];
 res[1] := x![1];
 fi;
 fi;
 ConvertToVectorRep(res);
 return res;
 end;

 # We collect (bX)^i mod f, i = 0..d*dK-1, and compute
 # the minimal polynomial of bX over F.
 # one
 vec := NullMat(1, d, F)[1];
 vec[1] := one;
 vecs := [];
 pols := [];
 zeroes := [];
 pmat := [];
 # X
 v := NullMat(1,deg,K)[1];
 v[1] := One(K);
 for i in [1..d+1] do
 if i <= d then
 Add(pmat,vec);
 fi;
 w := ShallowCopy(vec);
 p := ShallowCopy(zeroes);
 Add(p, one);
 ConvertToVectorRepNC(p, F);
 piv := PositionNonZero(w, 0);
 # reduce
 while piv <= d and IsBound(vecs[piv]) do
 x := -w[piv];
 if IsBound(pols[piv]) then
 AddCoeffs(p, pols[piv], x);
 fi;
 AddRowVector(w, vecs[piv], x, piv, d);
 piv := PositionNonZero(w,piv);
 od;
 if i <= d then
 x := Inverse(w[piv]);
 MultVector(p, x);
 MakeImmutable(p);
 pols[piv] := p;
 MultVector(w, x );
 MakeImmutable(w);
 vecs[piv] := w;
 Add(zeroes,zero);

 # multiply by bX and find next vec in tower basis
 v := b*v;
 c := -v[deg];
 for j in [deg, deg-1..2] do
 v[j] := v[j-1];
 od;
 v[1] := zK;
 if not IsZero(c) then
 for j in [1..Length(lcoeffs)] do
 v[j] := v[j] + c*lcoeffs[j];
 od;
 fi;
 vec := [];
 for c in v do
 Append(vec, co(c) * pK);
 od;
 ConvertToVectorRepNC(vec, F);
 fi;
 od;
 # Now the last p is the minimal polynomial over F
 # and pmat are the primitive powers in the tower basis for the new
 # extension.
 MakeImmutable(p);
 ConvertToMatrixRep(pmat);
 fi;
 # generate the new extension
 vnam := Concatenation("x", String(d));
 var := Indeterminate(F, vnam);
 ivar := IndeterminateNumberOfUnivariateLaurentPolynomial(var);
 Kp := AlgebraicExtensionNC(F, UnivariatePolynomial(F, p, ivar), vnam);

# temporary work around for a bug in GAP-dev
if Characteristic(K) > 2^16 then
 fam := ElementsFamily(FamilyObj(Kp));;
 fam!.reductionMat := List(fam!.reductionMat,List);
fi;

 Setter(IsStandardFiniteField)(Kp, true);
 Setter(PrimitivePowersInTowerBasis)(Kp, pmat);
 if dK = 1 then
 # identity matrix
 Setter(TowerBasis)(Kp, pmat);
 fi;
 # let elements know to be in standard field
 fam := FamilyObj(RootOfDefiningPolynomial(Kp));
 fam!.extType := Subtype(fam!.extType, IsStandardFiniteFieldElement);
 fam!.baseType := Subtype(fam!.baseType, IsStandardFiniteFieldElement);
 SetFilterObj(OneImmutable(Kp), IsStandardFiniteFieldElement);
 SetFilterObj(ZeroImmutable(Kp), IsStandardFiniteFieldElement);
 SetFilterObj(RootOfDefiningPolynomial(Kp), IsStandardFiniteFieldElement);

 return Kp;
end);

## <#GAPDoc Label="FF">
## <ManSection>
## <Heading>Constructing standard finite fields</Heading>
## <Func Name="StandardFiniteField" Arg="p, n"/>
## <Func Name="FF" Arg="p, n"/>
## <Returns>a finite field</Returns>
## <Func Name="StandardPrimeDegreePolynomial" Arg="p, r, k" />
## <Returns>a polynomial of degree <A>r</A></Returns>
## <Description>
## The arguments are a prime <A>p</A> and a positive integer
## <A>n</A>. The function <Ref Func="FF"/> (or its synomym <Ref
## Func="StandardFiniteField"/>) is one of the main functions of this
## package. It returns a standardized field <C>F</C> of order
## <M><A>p</A>^{<A>n</A>}</M>. It is implemented as a simple extension
## over the prime field <C>GF(p)</C> using <Ref BookName="Reference"
## Oper="AlgebraicExtension" />
## 
## The polynomials used for the prime degree extensions are
## accessible with <Ref Func="StandardPrimeDegreePolynomial"/>. For
## arguments <A>p, r, k</A> it returns the irreducible polynomial of
## degree <A>r</A> for the <A>k</A>-th iterated extension of degree
## <A>r</A> over the prime field. The polynomial is in the variable
## <C>x</C><Emph>r</Emph><C>_</C><Emph>k</Emph> and the coefficients can
## contain variables <C>x</C><Emph>r</Emph><C>_</C><Emph>l</Emph> with <M>l
## < k</M>.
## 
## <Example>gap> Fp := FF(2, 1);
## GF(2)
## gap> F := FF(2, 100);
## FF(2, 100)
## gap> Size(F);
## 1267650600228229401496703205376
## gap> p := NextPrimeInt(10^50);
## 100000000000000000000000000000000000000000000000151
## gap> K := FF(p, 60);
## FF(100000000000000000000000000000000000000000000000151, 60)
## gap> LogInt(Size(K), 10);
## 3000
## gap> F := FF(13, 9*5);
## FF(13, 45)
## gap> StandardPrimeDegreePolynomial(13, 3, 1);
## x3_1^3+Z(13)^7
## gap> StandardPrimeDegreePolynomial(13, 3, 2);
## x3_2^3-x3_1
## gap> StandardPrimeDegreePolynomial(13, 5, 1);
## x5_1^5+Z(13)^4*x5_1^2+Z(13)^4*x5_1-Z(13)^0
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
InstallGlobalFunction(StandardFiniteField, function(p, n)
 local F, id, ext, fac, lf, n1, nK, st, q1, l, K, lK, c, L, b;
 if not IsPrimeInt(p) then
 Error("StandardFiniteField: first argument must be a prime\n");
 fi;
 F := GF(p);
 # we cache extensions in prime field
 if not IsBound(F!.extensions) then
 SetIsStandardPrimeField(F, true);
 F!.extensions := [F];
 id := IdentityMat(1, F);
 ConvertToMatrixRep(id, p);
 Setter(PrimitivePowersInTowerBasis)(F, id);
 fi;
 ext := F!.extensions;
 if IsBound(ext[n]) then
 return ext[n];
 fi;

 # construct field recursively via prime degree extensions
 fac := Collected(Factors(n));
 lf := fac[Length(fac)];
 n1 := lf[1]^(lf[2]-1);
 nK := n/lf[1];
 st := SteinitzNumberForPrimeDegree(p, lf[1], lf[2]);
 q1 := p^n1;
 l := CoefficientsQadic(st, q1);
 K := StandardFiniteField(p, nK);
 lK := List(l, y-> EmbedSteinitz(p, n1, nK, y));
 c := List(lK, nr-> ElementSteinitzNumber(K, nr));
 # primitive element of new extension is product of prime power
 # degree generators, class of bX, we construct b (product of the
 # other prime power degree generators):
 b := ElementSteinitzNumber(K, p^(Position(StdMonDegs(nK), nK/n1)-1));
 L := _ExtensionWithTowerBasis(K, lf[1], c, b);
 ext[n] := L;
 return L;
end);

# default for other fields
InstallOtherMethod(IsStandardFiniteField, ["IsField"], ReturnFalse);

# maps between elements of standard finite field and its
# standard finite field tower
InstallMethod(TowerBasis, ["IsStandardFiniteField"], function(F)
 return PrimitivePowersInTowerBasis(F)^-1;
end);

# elements as coefficient vectors in tower basis
InstallMethod(AsVector, ["IsStandardFiniteFieldElement"], function(x)
 local F;
 F := FamilyObj(x)!.wholeField;
 return ExtRepOfObj(x) * PrimitivePowersInTowerBasis(F);
end);

InstallOtherMethod(AsVector,
 ["IsStandardFiniteField", "IsStandardFiniteFieldElement"],
function(F, x)
 return ExtRepOfObj(x) * PrimitivePowersInTowerBasis(F);
end);

# elements as polynomials
InstallMethod(GeneratorMonomials, [IsStandardFiniteField],
function(F)
 local res, d, f, Fp, s, a, i, v;
 res := rec(vars := []);
 d := DegreeOverPrimeField(F);
 if d = 1 then
 return res;
 fi;
 f := Collected(Factors(d));
 Fp := PrimeField(F);
 for a in f do
 res.(a[1]) := rec();
 for i in [1..a[2]] do
 s := Concatenation("x",String(a[1]),"_",String(i));
 v := Indeterminate(Fp, s);
 res.(a[1]).(i) := v;
 Add(res.vars, v);
 od;
 od;
 return res;
end);
InstallMethod(TowerBasisMonomials, [IsStandardFiniteField],
function(F)
 local d, m, l, o, res, b, i, a;
 d := DegreeOverPrimeField(F);
 m := GeneratorMonomials(F);
 l := StdMon(d)[1];
 o := One(PrimeField(F));
 res := [];
 for a in l do
 b := o;
 i := 1;
 while i < Length(a) do
 b := b*m.(a[i]).(a[i+1])^a[i+2];
 i := i+3;
 od;
 Add(res, b);
 od;
 return res;
end);
InstallOtherMethod(AsPolynomial, ["IsFFE"], IdFunc);
InstallMethod(AsPolynomial, ["IsStandardFiniteFieldElement"],
function(x)
 local F;
 F := FamilyObj(x)!.wholeField;
 return AsVector(x) * TowerBasisMonomials(F);
end);
# vice versa, we also support non-reduced polynomials
InstallMethod(ElementPolynomial, [IsStandardFiniteField, IsPolynomial],
function(F, pol)
 local gm, tbm, poss, a, tb, res;
 gm := GeneratorMonomials(F);
 if not IsBound(F!.gmeltvars) then
 tbm := TowerBasisMonomials(F);
 poss := List(gm.vars, x-> Position(tbm, x));
 a := PrimitiveElement(F);
 tb := TowerBasis(F);
 F!.gmeltvars := List(poss, i-> ValuePol(tb[i], a));
 fi;
 res := Value(pol, gm.vars, F!.gmeltvars);
 if not res in F then
 return fail;
 fi;
 return res;
end);

# miscellaneous utilities
InstallMethod(PrimeField, ["IsStandardFiniteField"],
 F -> FF(Characteristic(F), 1));

## <#GAPDoc Label="IsFF">
## <ManSection>
## <Heading>Filters for standard fields</Heading>
## <Prop Name="IsStandardPrimeField" Arg="F" />
## <Prop Name="IsStandardFiniteField" Arg="F" />
## <Filt Name="IsStandardFiniteFieldElement" Arg="x" Type="Category"/>
## <Returns><K>true</K> or <K>false</K> </Returns>
## <Description>
## These properties identify the finite fields constructed with <Ref
## Func="FF" />. Prime fields constructed as <C>FF(p, 1)</C> have the
## property <Ref Prop="IsStandardPrimeField"/>. They are identical with
## <C>GF(p)</C>, but calling them via <Ref Func="FF" /> we store some
## additional information in these objects.
## 
## The fields constructed by <C>FF(p,k)</C> with <C>k</C> <M> > 1</M>
## have the property <Ref Prop="IsStandardFiniteField"/>. Elements <A>x</A> in
## such a field are in <Ref Filt="IsStandardFiniteFieldElement"/>.
## 
## <Example>gap> F := FF(19,1);
## GF(19)
## gap> IsStandardFiniteField(F);
## false
## gap> IsStandardPrimeField(F);
## true
## gap> F := FF(23,48);
## FF(23, 48)
## gap> IsStandardFiniteField(F);
## true
## gap> IsStandardFiniteFieldElement(Random(F));
## true
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
InstallOtherMethod(IsStandardPrimeField, ["IsField"], function(K)
 local p;
 if not IsFinite(K) then
 return false;
 fi;
 p := Size(K);
 if not IsPrimeInt(p) then
 return false;
 fi;
 if K = FF(p,1) then
 return true;
 fi;
 return false;
end);

## <#GAPDoc Label="FFElmConv">
## <ManSection>
## <Heading>Maps for elements of standard finite fields</Heading>
## <Meth Name="AsVector" Label="for elements in standard finite fields"
## Arg="a"/>
## <Returns>a vector over prime field of <C>F</C> </Returns>
## <Meth Name="ElementVector" Arg="F, v"/>
## <Returns>an element in <C>F</C> </Returns>
## <Meth Name="AsPolynomial" Label="for elements in standard finite fields"
## Arg="a"/>
## <Returns>a polynomial in variables of the tower of <C>F</C> </Returns>
## <Meth Name="ElementPolynomial" Arg="F, pol"/>
## <Returns>an element in <C>F</C> </Returns>
## <Meth Name="SteinitzNumber" Arg="a"/>
## <Returns>an integer</Returns>
## <Meth Name="ElementSteinitzNumber" Arg="F, nr"/>
## <Returns>an element in <C>F</C></Returns>
## <Description>
## Here, <A>F</A> is always a standard finite field (<Ref
## Filt="IsStandardFiniteField"/>) and <A>a</A> is an element of <A>F</A>.
## 
## <Ref Meth="AsVector" Label="for elements in standard finite fields"/>
## returns the coefficient vector of <A>a</A> with respect to the tower
## basis of <A>F</A>. And vice versa <Ref Meth="ElementVector"/> returns
## the element of <A>F</A> with the given coefficient vector.
## 
## Similarly, <Ref Meth="AsPolynomial" Label="for elements in standard
## finite fields"/> returns the (reduced) polynomial in the
## indeterminates defining the tower of <A>F</A>. Here, for each prime
## <M>r</M> dividing the degree of the field the polynomial defining the
## <M>k</M>-th extension of degree <M>r</M> over the prime field is
## written in the variable <C>x</C><M>r</M><C>_</C><M>k</M>. And <Ref
## Meth="ElementPolynomial"/> returns the element of <A>F</A> represented
## by the given polynomial (which does not need to be reduced).
## 
## Finally, <Ref Meth="SteinitzNumber"/> returns the Steinitz number of
## <A>a</A>. And <Ref Meth="ElementSteinitzNumber"/> returns the element
## with given Steinitz number.
## <Example><![CDATA[gap> F := FF(17, 12);
## FF(17, 12)
## gap> a := PrimitiveElement(F);; a := a^11-3*a^5+a;
## ZZ(17,12,[0,1,0,0,0,14,0,0,0,0,0,1])
## gap> v := AsVector(a);
## < immutable compressed vector length 12 over GF(17) >
## gap> a = ElementVector(F, v);
## true
## gap> ExtRepOfObj(a) = v * TowerBasis(F);
## true
## gap> pol := AsPolynomial(a);;
## gap> ElementPolynomial(F, pol^10) = a^10;
## true
## gap> nr := SteinitzNumber(a);
## 506020624175737
## gap> a = ElementSteinitzNumber(F, nr);
## true
## gap> ## primitive element of FF(17, 6)
## gap> y := ElementSteinitzNumber(F, 17^5);
## ZZ(17,12,[0,0,1,0,0,0,12,0,0,0,5,0])
## gap> y = ValuePol([0,0,1,0,0,0,12,0,0,0,5,0], PrimitiveElement(F));
## true
## gap> x6 := Indeterminate(FF(17,1), "x6");;
## gap> MinimalPolynomial(FF(17,1), y, x6) = DefiningPolynomial(FF(17,6));
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
InstallMethod(ElementVector, ["IsStandardFiniteField", "IsRowVector"],
function(F, vec)
 local fam, l;
 fam := FamilyObj(PrimitiveElement(F));
 l := vec * TowerBasis(F);
 if ForAll([2..Length(l)], i-> IsZero(l[i])) then
 l := l[1];
 fi;
 return ObjByExtRep(fam, l);
end);

InstallOtherMethod(SteinitzNumber, ["IsFFE"], IntFFE);
InstallOtherMethod(SteinitzNumber,
 ["IsStandardPrimeField", "IsRingElement"],
function(F, c)
 return IntFFE(c);
end);
InstallMethod(SteinitzNumber, ["IsStandardFiniteField", "IsRingElement"],
function(F, c)
 local v;
 v := List(ExtRepOfObj(c) * PrimitivePowersInTowerBasis(F), IntFFE);
 return ValuePol(v, Characteristic(F));
end);
InstallOtherMethod(SteinitzNumber, ["IsStandardFiniteFieldElement"],
function(x)
 return SteinitzNumber(FamilyObj(x)!.wholeField, x);
end);

# reverse
InstallOtherMethod(ElementSteinitzNumber,
 ["IsStandardPrimeField", "IsInt"],
function(F, nr)
 return nr*One(F);
end);
InstallMethod(ElementSteinitzNumber, ["IsStandardFiniteField", "IsInt"],
function(F, nr)
 local p, fam, tc, l;
 if nr < 0 or nr >= Size(F) then
 return fail;
 fi;
 if nr = 0 then
 return Zero(F);
 fi;
 p := Characteristic(F);
 fam := FamilyObj(PrimitiveElement(F));
 tc := One(GF(p))*CoefficientsQadic(nr, p);
 ConvertToVectorRep(tc, p);
 l := tc * TowerBasis(F);
 if ForAll([2..Length(l)], i-> IsZero(l[i])) then
 l := l[1];
 fi;
 return ObjByExtRep(fam, l);
end);

InstallMethod(ViewString, ["IsStandardFiniteField"], function(F)
 return Concatenation("FF(", String(Characteristic(F)),
 ", ", String(DegreeOverPrimeField(F)), ")");
end);
InstallMethod(ViewObj, ["IsStandardFiniteField"], function(F)
 Print(ViewString(F));
end);
InstallMethod(PrintString, ["IsStandardFiniteField"], ViewString);

InstallMethod(PrintObj, ["IsStandardFiniteField"], function(F)
 Print(PrintString(F));
end);

# helper: describe monomials in tower basis and their degrees
InstallGlobalFunction(StdMon, function(n)
 local rs, res, deg, r, k, new, ndeg, i, j;
 rs := Factors(n);
 res := [[]];
 deg := [1];
 for i in [1..Length(rs)] do
 r := rs[i];
 if i = 1 or rs[i-1] <> r then
 k := 1;
 else
 k := k+1;
 fi;
 new := ShallowCopy(res);
 ndeg := ShallowCopy(deg);
 for j in [1..r-1] do
 Append(new, List(res, a-> Concatenation(a, [r,k,j])));
 Append(ndeg, List(deg, a-> LcmInt(a,r^k)));
 od;
 res := new;
 deg := ndeg;
 od;
 return [res, deg];
end);

# just the degrees
InstallGlobalFunction(StdMonDegs, function(n)
 local f, a, res, new, i;
 if n = 1 then return [1]; fi;
 f := Collected(Factors(n));
 a := f[Length(f)];
 res := StdMonDegs(n/a[1]);
 new := List(res, l-> LcmInt(l, a[1]^a[2]));
 for i in [1..a[1]-1] do
 Append(res, new);
 od;
 return res;
end);
# map of monomials for degree n into monomials of degree m (by positions)
InstallGlobalFunction(StdMonMap, function(n, m)
 local d;
 d := StdMonDegs(m);
 return Filtered([1..Length(d)], i-> n mod d[i] = 0);
end);

# Embedding of element in FF(p,n) into FF(p,m) by Steinitz numbers
InstallGlobalFunction(EmbedSteinitz, function(p, n, m, nr)
 local l, map, c;
 if n=m or nr = 0 then return nr; fi;
 l := CoefficientsQadic(nr, p);
 map := StdMonMap(n, m){[1..Length(l)]};
 c := 0*[1..map[Length(map)]];
 c{map} := l;
 return ValuePol(c, p);
end);

InstallMethod(ExtRepOfObj,"baseFieldElm",true,
 [IsAlgebraicElement and IsAlgBFRep],0,
function(e)
 local f,l;
 f:=FamilyObj(e);
 l := 0*ShallowCopy(f!.polCoeffs{[1..f!.deg]});
 l[1] := e![1];
 MakeImmutable(l);
 return l;
end);

InstallMethod(Embedding, ["IsStandardPrimeField", "IsStandardPrimeField"],
function(K, L)
 local emb;
 if K <> L then
 Error("Embedding need identical prime fields.");
 fi;
 emb := MappingByFunction(K, L, IdFunc, false, IdFunc);
 SetFilterObj(emb, IsStandardFiniteFieldEmbedding);
 return emb;
end);
InstallMethod(Embedding, ["IsStandardPrimeField", "IsStandardFiniteField"],
function(K, L)
 local p, famL, fun, pre, emb;
 p := Characteristic(K);
 famL := FamilyObj(PrimitiveElement(L));
 fun := function(x)
 return ObjByExtRep(famL, x);
 end;
 pre := function(y)
 if IsAlgBFRep(y) then
 return y![1];
 else
 return fail;
 fi;
 end;
 emb := MappingByFunction(K, L, fun, false, pre);
 SetFilterObj(emb, IsStandardFiniteFieldEmbedding);
 return emb;
end);

## <#GAPDoc Label="FFEmbedding">
## <ManSection>
## <Meth Name="Embedding" Label="for standard finite fields" Arg="H, F"/>
## <Returns>a field homomorphism </Returns>
## <Description>
## Let <A>F</A> and <A>H</A> be standard finite fields and <A>H</A> be
## isomorphic to a subfield of <A>F</A>. This function returns the canonical
## embedding of <A>H</A> into <A>F</A>.
## 
## <Example>gap> F := FF(7, 360);
## FF(7, 360)
## gap> H := FF(7, 45);
## FF(7, 45)
## gap> emb := Embedding(H, F);
## MappingByFunction( FF(7, 45), FF(7, 360), function( x ) ... end )
## gap> y := PrimitiveElement(H);
## ZZ(7,45,[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
## 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
## gap> x := y^emb;;
## gap> ((y+One(H))^12345)^emb = (x+One(F))^12345;
## true
## gap> PreImageElm(emb, x^5);
## ZZ(7,45,[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
## 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
## gap> PreImageElm(emb, PrimitiveElement(F));
## fail
## gap> SteinitzNumber(y);
## 13841287201
## gap> SteinitzNumber(x) mod 10^50;
## 72890819326613454654477690085519113574118965817601
## gap> SteinitzPair(x);
## [ 45, 13841287201 ]
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
InstallMethod(Embedding, ["IsStandardFiniteField", "IsStandardFiniteField"],
function(K, L)
 local p, d, a, monK, monL, map, z, famL, famK, fun, imgen, fun2, pre, emb;
 p := Characteristic(K);
 if Characteristic(L) <> p then
 Error("different characteristic");
 fi;
 d := DegreeOverPrimeField(L);
 a := DegreeOverPrimeField(K);
 if not d mod a = 0 then
 Error("not a subfield");
 fi;
 if not IsBound(K!.embcache) then
 K!.embcache := rec();
 fi;
 if IsBound(K!.embcache.(d)) then
 return K!.embcache.(d);
 fi;
 monK := StdMon(a);
 monL := StdMon(d);
 map := List(monK[1], x-> Position(monL[1], x));
 z := AsVector(Zero(L));
 famL := FamilyObj(PrimitiveElement(L));
 famK := FamilyObj(PrimitiveElement(K));
 fun := function(x)
 local v, res, l;
 v := AsVector(x);
 res := ShallowCopy(z);
 res{map} := v;
 l := res*TowerBasis(L);
 if ForAll([2..Length(l)], i-> IsZero(l[i])) then
 l := l[1];
 fi;
 return ObjByExtRep(famL, l);
 end;
## # Maybe this version of "fun" can be made faster?
## imgen := fun(PrimitiveElement(K));
## fun2 := function(x)
## local c;
## c := x![1];
## if not IsList(c) then
## return c*One(L);
## fi;
## return ValuePol(c, imgen);
## end;
 pre := function(y)
 local v, l;
 v := AsVector(L, y);
 if ForAny([1..d], i-> not (i in map or IsZero(v[i]))) then
 return fail;
 fi;
 l := v{map};
 if ForAll([2..a], i-> IsZero(l[i])) then
 return ObjByExtRep(famK, l[1]);
 else
 return ObjByExtRep(famK, l*TowerBasis(K));
 fi;
 end;
 emb := MappingByFunction(K, L, fun, false, pre);
 SetFilterObj(emb, IsStandardFiniteFieldEmbedding);
 K!.embcache.(d) := emb;
 return emb;
end);
InstallMethod(IsSurjective, ["IsStandardFiniteFieldEmbedding"],
function(emb)
 return DegreeOverPrimeField(Source(emb)) = DegreeOverPrimeField(Range(emb));
end);
InstallOtherMethod(PreImageElm,
 ["IsStandardFiniteFieldEmbedding", "IsRingElement"],
function(emb, y)
 return emb!.prefun(y);
end);

## <#GAPDoc Label="SteinitzPair">
## <ManSection>
## <Oper Name="SteinitzPair" Arg="a"/>
## <Returns>a pair of integers</Returns>
## <Meth Name="SteinitzPair" Label="for Steinitz number" Arg="K, snr"/>
## <Returns>a pair of integers</Returns>
## <Meth Name="SteinitzNumber" Label="for Steinitz pair" Arg="K, pair"/>
## <Returns>an integer</Returns>
## <Description>
## The argument <A>a</A> must be an element in <Ref
## Filt="IsStandardFiniteFieldElement"/>. Then <Ref Oper="SteinitzPair"/>
## returns a pair <C>[d, nr]</C> where <C>d</C> is the degree of <A>a</A>
## over the prime field <C>FF(p, 1)</C> and <C>nr</C> is the Steinitz
## number of <A>a</A> considered as element of <C>FF(p, d)</C>.
## 
## In the second variant a standard finite field <A>K</A> is given and the
## Steinitz number of an element in <A>K</A> and the result is the Steinitz
## pair of the corresponding element.
## 
## The inverse map is provided by a method for <Ref Meth="SteinitzNumber"
## Label="for Steinitz pair"/> which gets a standard finite field and a
## Steinitz pair.
## <Example>gap> F := FF(7, 360);
## FF(7, 360)
## gap> t := ElementSteinitzNumber(F, 7^10);; # prim. elt of FF(7,12)
## gap> sp := SteinitzPair(t);
## [ 12, 117649 ]
## gap> H := FF(7, 12);
## FF(7, 12)
## gap> b := ElementSteinitzNumber(H, 117649);
## ZZ(7,12,[0,1,0,0,0,0,0,0,0,0,0,0])
## gap> Value(MinimalPolynomial(FF(7,1), t), b);
## ZZ(7,12,[0])
## gap> nr := SteinitzNumber(t);
## 282475249
## gap> nr = SteinitzNumber(F, sp);
## true
## gap> sp = SteinitzPair(F, nr);
## true
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
# SteinitzPair(x): [deg, nr] where deg is the degree of x over prime field
# and nr the Steinitz number of x as element in FF(p, deg).
BindGlobal("StPairIntVec", function(K, v)
 local p, d, map, ind, sd, vv;
 p := Characteristic(K);
 d := DegreeOverPrimeField(K);
 map := StdMonDegs(d);
 ind := Filtered([1..d], i-> IsBound(v[i]) and not IsZero(v[i]));
 if Length(ind) = 0 then
 return [1,0];
 fi;
 sd := Lcm(Set(map{ind}));
 ind := Filtered([1..d], i-> sd mod map[i] = 0);
 while ind[Length(ind)] > Length(v) do
 Remove(ind);
 od;
 vv := v{ind};
 return [sd, ValuePol(vv, p)];
end);
GAPInfo.tmpmeth := function(F, x)
 return StPairIntVec(F, List(AsVector(x), IntFFE));
end;
InstallOtherMethod(SteinitzPair,
 ["IsStandardFiniteField", "IsStandardFiniteFieldElement"], GAPInfo.tmpmeth);
Unbind(GAPInfo.tmpmeth);
InstallOtherMethod(SteinitzPair, ["IsStandardPrimeField", "IsFFE"],
function(F, x)
 return [1, SteinitzNumber(F,x)];
end);

# with Steinitz number instead of element
GAPInfo.tmpmeth := function(F, nr)
 local p;
 p := Characteristic(F);
 return StPairIntVec(F, CoefficientsQadic(nr, p));
end;
InstallOtherMethod(SteinitzPair,
 ["IsStandardFiniteField", "IsInt"], GAPInfo.tmpmeth);
Unbind(GAPInfo.tmpmeth);
InstallOtherMethod(SteinitzPair, ["IsStandardPrimeField", "IsInt"],
function(F, nr)
 return [1, nr];
end);

InstallMethod(SteinitzPair, ["IsStandardFiniteFieldElement"],
function(x)
 return SteinitzPair(FamilyObj(x)!.wholeField, x);
end);
# works only for prime fields
InstallOtherMethod(SteinitzPair, ["IsStandardPrimeField","IsFFE"],
{F, x}-> [1, IntFFE(x)]);
InstallOtherMethod(SteinitzPair, ["IsFFE"], x-> [1, IntFFE(x)]);

# convert Steinitz pair in Steinitz number
GAPInfo.tmp :=
function(K, st)
 local p, d, v, map, ind, vv;
 p := Characteristic(K);
 d := DegreeOverPrimeField(K);
 if st[1] = d then
 return st[2];
 fi;
 v := CoefficientsQadic(st[2], p);
 map := StdMonDegs(d);
 # indices of subsequence of tower basis of subfield
 ind := Filtered([1..d], i-> st[1] mod map[i] = 0);
 if Length(ind) > Length(v) then
 ind := ind{[1..Length(v)]};
 fi;
 vv := 0*[1..d];
 vv{ind} := v;
 return ValuePol(vv, p);
end;
InstallOtherMethod(SteinitzNumber, ["IsStandardFiniteField", "IsList"],
GAPInfo.tmp);
InstallOtherMethod(SteinitzNumber, ["IsStandardPrimeField", "IsList"],
function(K, pair)
 if pair[1] <> 1 then
 Error("Steinitz pair not in prime field.");
 fi;
 return pair[2];
end);

## <#GAPDoc Label="SteinitzPairConwayGenerator">
## <ManSection>
## <Func Name="SteinitzPairConwayGenerator" Arg="F"/>
## <Returns>a pair of integers </Returns>
## <Description>
## For a standard finite field <A>F</A> of order <M>q</M> for which a Conway
## polynomial (see <Ref BookName="Reference" Func="ConwayPolynomial"/>) is
## known this function returns the <Ref Oper="SteinitzPair"/> for the element
## of <A>F</A> corresponding to <C>Z(q)</C> (which is by definition the zero
## of the Conway polynomial in <A>F</A> with the smallest Steinitz number
## which is compatible with the choice in all proper subfields).
## 
## This is used to construct the
## <Ref Func="StandardIsomorphismGF"/> for <A>F</A>.
## <Example>gap> F := FF(23,18);
## FF(23, 18)
## gap> st := SteinitzPairConwayGenerator(F);
## [ 18, 1362020736983803830549380 ]
## gap> st9 := SteinitzPairConwayGenerator(FF(23,9));
## [ 9, 206098743447 ]
## gap> st6 := SteinitzPairConwayGenerator(FF(23,6));
## [ 6, 45400540 ]
## gap> z := ElementSteinitzNumber(F, st[2]);;
## gap> z9 := ElementSteinitzNumber(F, SteinitzNumber(F, st9));;
## gap> z6 := ElementSteinitzNumber(F, SteinitzNumber(F, st6));;
## gap> e9 := (Size(F)-1)/(23^9-1);
## 1801152661464
## gap> e6 := (Size(F)-1)/(23^6-1);
## 21914624580056211
## gap> z9 = z^e9;
## true
## gap> z6 = z^e6;
## true
## gap> l := Filtered(ZeroesConway(F), x-> x^e9 = z9 and x^e6 = z6);;
## gap> List(l, SteinitzNumber);
## [ 1362020736983803830549380 ]
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
InstallOtherMethod(SteinitzPairConwayGenerator, ["IsStandardPrimeField"],
function(K)
 local pl;
 pl := ConwayPol(Characteristic(K), 1) * One(K);
 return [1, SteinitzNumber(K, -pl[1])];
end);

InstallMethod(SteinitzPairConwayGenerator, ["IsStandardFiniteField"],
function(K)
 local d, p, rs, compat, exp, L, c, emb, pl, z, st, i, r;
 d := DegreeOverPrimeField(K);
 p := Characteristic(K);
 if not IsCheapConwayPolynomial(p, d) then
 return fail;
 fi;
 rs := Set(Factors(d));
 compat := [];
 exp := [];
 for r in rs do
 L := FF(p, d/r);
 c := SteinitzPairConwayGenerator(L);
 emb := Embedding(L, K);
 Add(compat, Image(emb, ElementSteinitzNumber(L,c[2])));
 Add(exp, (Size(K)-1)/(Size(L)-1));
 od;

 pl := ConwayPol(p, d) * One(K);
 #z := FindConjugateZeroes(K, pl, p);
 z := ZeroesConway(K);
 st := List(z, c-> SteinitzNumber(K, c));
 SortParallel(st, z);
 # now find Steinitz smallest zero compatible with compat
 i := First([1..d], i-> ForAll([1..Length(rs)], j-> z[i]^exp[j] = compat[j]));
 return SteinitzPair(K, z[i]);
end);

## <#GAPDoc Label="StandardIsomorphismGF">
## <ManSection>
## <Func Name="StandardIsomorphismGF" Arg="F" />
## <Returns>a field isomorphism </Returns>
## <Description>
## The argument <A>F</A> must be a standard finite field, say
## <C>FF(p,n)</C> such that &GAP; can generate <C>GF(p,n)</C>. This
## function returns the field isomorphism from <C>GF(p,n)</C> to <A>F</A>,
## which sends <C>Z(p,n)</C> to the element with Steinitz pair computed by
## <Ref Func="SteinitzPairConwayGenerator" />.
## 
## <Example>gap> F := FF(13,21);
## FF(13, 21)
## gap> iso := StandardIsomorphismGF(F);
## MappingByFunction( GF(13^21), FF(13, 21), function( x ) ... end )
## gap> K := GF(13,21);
## GF(13^21)
## gap> x := Random(K);;
## gap> l := [1,2,3,4,5];;
## gap> ValuePol(l, x)^iso = ValuePol(l, x^iso);
## true
## gap> y := ElementSteinitzNumber(F, SteinitzPairConwayGenerator(F)[2]);;
## gap> PreImageElm(iso, y);
## z
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
InstallGlobalFunction(StandardIsomorphismGF,
function(L)
 local p, d, K, z, fun, a, mat, imat, zz, pre, emb, i;
 p := Characteristic(L);
 d := DegreeOverPrimeField(L);
 if IsBound(L!.isocache) then
 return L!.isocache;
 fi;
 if d = 1 then
 emb := IdentityMapping(L);
 SetFilterObj(emb, IsFieldHomomorphism and IsBijective);
 return emb;
 fi;
 K := GF(p,d);
 z := ElementSteinitzNumber(L, SteinitzPairConwayGenerator(L)[2]);
 fun := function(x)
 local c, bas;
 if IsPositionalObjectRep(x) then
 c := x![1];
 else
 bas := CanonicalBasis(K);
 c := Coefficients(bas, x);
 fi;
 return ValuePol(c, z);
 end;
 a := One(L);
 mat := [];
 for i in [1..d] do
 Add(mat, ExtRepOfObj(a));
 a := a*z;
 od;
 imat := mat^-1;
 zz := Z(Size(K));
 pre := function(y)
 return ValuePol(ExtRepOfObj(y)*imat, zz);
 end;
 emb := MappingByFunction(K, L, fun, false, pre);
 SetFilterObj(emb, IsFieldHomomorphism and IsBijective);
 L!.isocache := emb;
 return emb;
end);

## <#GAPDoc Label="FFArith">
## <ManSection>
## <Oper Name="ZZ" Arg="p, n, coeffs" />
## <Oper Name="ZZ" Arg="p, n, ffe" Label="for IsFFE" />
## <Returns>an element in <C>FF(<A>p</A>, <A>n</A>)</C></Returns>
## <Description>
## For a prime <A>p</A>, positive integer <A>n</A> and an integer list
## <A>coeffs</A> this function returns the element in <C>FF(<A>p</A>,
## <A>n</A>)</C> represented by the polynomial with coefficient list
## <A>coeffs</A> modulo <A>p</A>. Elements in standard finite fields are
## also printed in this way.
## 
## For convenience the third argument <A>ffe</A> can be in `GF(p,n)` (see
## <Ref BookName="Reference" Func="GF" Label="for characteristic and
## degree" /> and <Ref BookName="Reference" Filt="IsFFE"/>). This returns
## the image of <A>ffe</A> under the <Ref Func="StandardIsomorphismGF"/>
## of <C>FF(<A>p</A>,<A>n</A>)</C>.
## <Example>gap> x := ZZ(19,5,[1,2,3,4,5]);
## ZZ(19,5,[1,2,3,4,5])
## gap> a := PrimitiveElement(FF(19,5));
## ZZ(19,5,[0,1,0,0,0])
## gap> x = [1,2,3,4,5]*[a^0,a^1,a^2,a^3,a^4];
## true
## gap> One(FF(19,5)); # elements in prime field abbreviated
## ZZ(19,5,[1])
## gap> One(FF(19,5)) = ZZ(19,5,[1]);
## true
## gap> ZZ(19,5,Z(19^5)); # zero of ConwayPolynomial(19,5)
## ZZ(19,5,[12,5,3,4,5])
## </Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Func Name="MoveToSmallestStandardField" Arg="x" />
## <Meth Name="\+" Arg="x, y" Label="for standard finite field elements" />
## <Meth Name="\*" Arg="x, y" Label="for standard finite field elements" />
## <Meth Name="\-" Arg="x, y" Label="for standard finite field elements" />
## <Meth Name="\/" Arg="x, y" Label="for standard finite field elements" />
## <Returns>a field element </Returns>
## <Description>
## Here <A>x</A> and <A>y</A> must be elements in standard finite fields
## (of the same characteristic).
## 
## Then <Ref Func="MoveToSmallestStandardField" /> returns the element
## <A>x</A> as element of the smallest possible degree extension over the
## prime field.
## 
## The arithmetic operations are even possible when <A>x</A> and <A>y</A>
## are not represented as elements in the same field. In this case the
## elements are first mapped to the smallest field containing both.
## <Example>gap> F := FF(1009,4);
## FF(1009, 4)
## gap> G := FF(1009,6);
## FF(1009, 6)
## gap> x := (PrimitiveElement(F)+One(F))^13;
## ZZ(1009,4,[556,124,281,122])
## gap> y := (PrimitiveElement(G)+One(G))^5;
## ZZ(1009,6,[1,5,10,10,5,1])
## gap> x+y;
## ZZ(1009,12,[557,0,936,713,332,0,462,0,843,191,797,0])
## gap> x-y;
## ZZ(1009,12,[555,0,73,713,677,0,97,0,166,191,212,0])
## gap> x*y;
## ZZ(1009,12,[253,289,700,311,109,851,345,408,813,657,147,887])
## gap> x/y;
## ZZ(1009,12,[690,599,714,648,184,217,563,130,251,675,73,782])
## gap> z := -y + (x+y);
## ZZ(1009,12,[556,0,0,713,0,0,784,0,0,191,0,0])
## gap> SteinitzPair(z);
## [ 4, 125450261067 ]
## gap> x=z;
## true
## gap> MoveToSmallestStandardField(z);
## ZZ(1009,4,[556,124,281,122])
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
# creating finite field elements
InstallMethod(ZZ, ["IsPosInt", "IsPosInt", "IsList"],
function(p,d,c)
 local F, i, fam;
 F := FF(p,d);
 if ForAll([2..Length(c)], i-> c[i] = 0) then
 return c[1] * One(F);
 fi;
 if Length(c) < d then
 c := ShallowCopy(c);
 for i in [Length(c)+1..d] do
 c[i] := 0;
 od;
 fi;
 fam := FamilyObj(PrimitiveElement(F));
 c := [One(FF(p,1)) * c];
 ConvertToVectorRep(c[1], p);
 Objectify(fam!.extType, c);
 return c;
end);
# utility method to embed FFE into standard field
InstallOtherMethod(ZZ, ["IsPosInt", "IsPosInt", "IsFFE"],
function(p,d,x)
 local F, emb;
 F := FF(p,d);
 emb := StandardIsomorphismGF(F);
 return x^emb;
end);

# nicer print/view for standard finite field elements
InstallMethod(PrintString, ["IsStandardFiniteFieldElement"],
function(x)
 local F, c, res;
 F := FamilyObj(x)!.wholeField;
 c := x![1];
 if IsFFE(c) then c := [c]; fi;
 res := Concatenation( "ZZ(", String(Characteristic(F)),",",
 String(DegreeOverPrimeField(F)),",",String(List(c, IntFFE)),")");
 RemoveCharacters(res, " ");
 res := SubstitutionSublist(res, ",", "\<,\>");
 return res;
end);
InstallMethod(PrintObj, ["IsStandardFiniteFieldElement"],
 function(x) Print(PrintString(x)); end);
InstallMethod(ViewString, ["IsStandardFiniteFieldElement"], PrintString);
InstallMethod(String, ["IsStandardFiniteFieldElement"],
 x-> StripLineBreakCharacters(PrintString(x)));

# arithmetic for elements from different standard fields
InstallGlobalFunction(MoveToCommonStandardField, function(a, b)
 local Fa, Fb, p, da, db, d, F;
 Fa := FamilyObj(a)!.wholeField;
 Fb := FamilyObj(b)!.wholeField;
 p := Characteristic(Fa);
 if p <> Characteristic(Fb) then Error("different characteristic"); fi;
 da := DegreeOverPrimeField(Fa);
 db := DegreeOverPrimeField(Fb);
 d := LcmInt(da, db);
 F := FF(p, d);
 if da < d then
 a := a^Embedding(Fa, F);
 fi;
 if db < d then
 b := b^Embedding(Fb, F);
 fi;
 return [a, b];
end);
InstallMethod(\+, IsNotIdenticalObj, ["IsStandardFiniteFieldElement",
"IsStandardFiniteFieldElement"], function(a, b)
 return CallFuncList(\+, MoveToCommonStandardField(a, b));
end);
InstallMethod(\*, IsNotIdenticalObj, ["IsStandardFiniteFieldElement",
"IsStandardFiniteFieldElement"], function(a, b)
 return CallFuncList(\*, MoveToCommonStandardField(a, b));
end);
InstallMethod(\=, IsNotIdenticalObj, ["IsStandardFiniteFieldElement",
"IsStandardFiniteFieldElement"], function(a, b)
 return Characteristic(a) = Characteristic(b) and
 SteinitzPair(a) = SteinitzPair(b);
end);
# utility to represent element in smallest field
InstallGlobalFunction(MoveToSmallestStandardField, function(a)
 local Fa, d, st, F;
 if IsFFE(a) then
 # also handle elements in GF(p,n)
 d := DegreeOverPrimeField(DefaultField(a));
 if d = 1 then return a; fi;
 a := a^StandardIsomorphismGF(FF(Characteristic(a), d));
 fi;
 Fa := FamilyObj(a)!.wholeField;
 d := DegreeOverPrimeField(Fa);
 st := SteinitzPair(a);
 if st[1] = d then
 return a;
 else
 F := FF(Characteristic(Fa), st[1]);
 return PreImageElm(Embedding(F, Fa), a);
 fi;
end);

Quelle StandardFF.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.41 Sekunden (vorverarbeitet) ]