/usr/share/gap/lib/ffeconway.gi

#############################################################################
##
#W  ffeconway.gi               GAP library                       Steve Linton
##
##
#Y  Copyright (C) 2005 The GAP Group
##
##  This file contains methods for `FFE's represented as library objects by
##  coefficients of polynomials modulo the Conway polynomial.
##

#############################################################################
##
#R IsCoeffsModConwayPolRep( <obj> )
##
## An element in this representation is stored a three component 
## PositionalObject
## 
## The first component is a mutable vector giving the coefficients of a polynomial
## over a prime field. Where appropriate, this should be compressed.
##
## The second component is an integer specifying the degree of the field extension
## over the prime field in which this element is written. 
##
## The third component may hold the representation of the element written over
## the field extension that it generates. If this is 'fail' then this is not known
## if it is 'false' then the element is known to be irreducible. This value may be 
## an internal FFE or a ZmodpZ object.
##
##
##  

BindGlobal("IsCoeffsModConwayPolRep", 
        NewRepresentation( "IsCoeffsModConwayPolRep", IsPositionalObjectRep,3));

#############################################################################
##
#V FFECONWAY is a holder for private function
##

BindGlobal("FFECONWAY", rec());

#############################################################################
##
#F FFECONWAY.ZNC(<p>,<d>) .. construct a primitive root
##
## this function also deals with construction and caching of the 
## Conway Polynomial and associated data. It must always be called before
## any computation with elements of GF(p^d)
##
## To support computing with these objects, a variety of data is stored in the 
## FFEFamily:
##
## 'fam!.ConwayFldEltDefaultType' contains the type of the field elements in this
##                                characteristic and representation
## 'fam!.ConwayPolCoeffs[d]'   contains the coefficients of the Conway Polynomial
##                               for GF(p^d)
## 'fam!.ConwayFldEltReducers[d]' contains a function which will take a mutable 
##                               vector of FFEs in compressed format (if appropriate)
##                               reduce it modulo the Conway polynomial and fix its 
##                               length to be exactly 'd'
## 'fam!.ZCache[d]'            contains 'Z(p,d)' once it has been computed.
##

FFECONWAY.SetUpConwayStuff := function(p,d)
    local   fam,  cp,  cps,  i;
    fam := FFEFamily(p);
    if not IsBound(fam!.ConwayPolCoeffs) then
        fam!.ConwayPolCoeffs := [];
        fam!.ConwayFldEltReducers := [];
    fi;
    if not IsBound(fam!.ConwayPolCoeffs[d]) then
        if not IsCheapConwayPolynomial(p,d) then
            Error("Conway Polynomial ",p,"^",d,
                  " will need to computed and might be slow\n", "return to continue");
        fi;  
        cp := CoefficientsOfUnivariatePolynomial(ConwayPolynomial(p,d));
        fam!.ConwayPolCoeffs[d] := cp;
        #
        # various cases for reducers 
        #
        if p = 2 then
            fam!.ConwayFldEltReducers[d] := function(v)
                REDUCE_COEFFS_GF2VEC(v,Length(v),cp,d+1);
                RESIZE_GF2VEC(v,d);
            end;
        elif p <= 256 then
            #
            # We can save time on repeated reductions using
            # pre-computed shifts
            #
            cps := MAKE_SHIFTED_COEFFS_VEC8BIT(cp,d+1);
            fam!.ConwayFldEltReducers[d] := function(v)
                REDUCE_COEFFS_VEC8BIT(v,Length(v),cps);
                RESIZE_VEC8BIT(v,d);
            end;
        else
            #
            # Need to adjust the length "by hand"
            #
            fam!.ConwayFldEltReducers[d] := function(v)
                ReduceCoeffs(v,Length(v),cp,d+1);
                if Length(v) < d then
                    PadCoeffs(v,d);
                elif Length(v) > d then
                    for i in [d+1..Length(v)] do
                        Unbind(v[i]);
                    od;
                fi;
            end;
        fi;
        
    fi;
end;    


FFECONWAY.ZNC := function(p,d)
    local   fam,  zc,  v;
    fam := FFEFamily(p);
    if not IsBound(fam!.ZCache) then
        fam!.ZCache := [];
    fi;
    zc := fam!.ZCache;
    if not IsBound(zc[d]) then
        if not IsBound(fam!.ConwayFldEltDefaultType) then
            fam!.ConwayFldEltDefaultType := NewType(fam, IsCoeffsModConwayPolRep and IsLexOrderedFFE);
        fi;
        FFECONWAY.SetUpConwayStuff(p,d);
        #
        # Finally make the element 
        # 'false' in the third component because we know it is 
        # irreducible
        #
        v := ListWithIdenticalEntries(d,0*Z(p));
        v[2] := Z(p)^0;
        ConvertToVectorRep(v,p);
        zc[d] := Objectify(fam!.ConwayFldEltDefaultType, [v,d,false]);
    fi;
    return zc[d];
end;

#############################################################################
##
#M Z(p,d), Z(q) .. 
##
##     check various things and call FFECONWAY.ZNC

InstallOtherMethod(ZOp, 
        [IsPosInt, IsPosInt],
        function(p,d)
    local   q;
    q := p^d;
    if q <= MAXSIZE_GF_INTERNAL or d =1 then
        return Z(q);
    fi;
    return FFECONWAY.ZNC(p,d);
end);

InstallMethod(ZOp,
        [IsPosInt],
        function(q)
    local   p,  d;
    if q <= MAXSIZE_GF_INTERNAL then
        TryNextMethod(); # should never happen
    fi;
    p := SmallestRootInt(q);
    d := LogInt(q,p);
    Assert(1, q=p^d);
    Assert(2, IsProbablyPrimeInt(p));
    if d > 1 then
        return FFECONWAY.ZNC(p,d);
    fi;
    TryNextMethod();
end);

        

#############################################################################
##
#M  PrintObj( <ffe> ) 
#M  String( <ffe> )
#M  ViewObj( <ffe> )
#M  ViewString( <ffe> )
#M  Display( <ffe> )
#M  DisplayString( <ffe> )
##
## output methods
##

InstallMethod(String,"For large finite field elements",
        [IsFFE and IsCoeffsModConwayPolRep], 
        function(x)
    local   started,  coeffs,  fam,  s,  str,  i;
    if not IsBool(x![3]) then
        return String(x![3]);
    fi;
    started := false;
    coeffs := x![1];
    fam := FamilyObj(x);
    s := Concatenation("Z(",String(fam!.Characteristic),",",String(x![2]),")");
    if Length(coeffs) = 0 then 
        str := "0*";
        Append(str,s);
        return str;
    fi;
    str := "";
    if not IsZero(coeffs[1]) then
        Append(str,String(coeffs[1]));
        started := true;
    fi;
    for i in [2..Length(coeffs)] do
        if not IsZero(coeffs[i]) then
            if started then
                Add(str,'+');
            fi;
            if not IsOne(coeffs[i]) then
                Append(str,String(IntFFE(coeffs[i])));
                Add(str,'*');
            fi;
            Append(str,s);
            if i > 2 then
                Add(str,'^');
                Append(str,String(i-1));
            fi;
            started := true;
        fi;
    od;
    if not started then
        str := "0*";
        Append(str,s);
    fi;
    return str;
end);

InstallMethod(PrintObj, "for large finite field elements (use String)",
        [IsFFE and IsCoeffsModConwayPolRep], 
        function(x)
    Print(String(x));
end);

BindGlobal( "DisplayStringForLargeFiniteFieldElements",
  function(x)
    local   s,  j,  a;
    if IsZero(x) then
        return "0z\n";
    elif IsOne(x) then
        return "z0\n";
    fi;
    s := "";
    for j in [0..x![2]-1] do
        a := IntFFE(x![1][j+1]);
        if a <> 0 then
            if Length(s) <> 0 then
                Append(s,"+");
            fi;
            if a <> 1 or j = 0 then
                Append(s,String(a));
            fi;
            if j <> 0 then
                Append(s,"z");
                if j <> 1 then
                    Append(s,String(j));
                fi;
            fi;
        fi;
    od;
    Add(s,'\n');
    return s;
  end );

InstallMethod(DisplayString,"For large finite field elements",
        [IsFFE and IsCoeffsModConwayPolRep], 
        DisplayStringForLargeFiniteFieldElements );

InstallMethod(Display,"For large finite field elements",
        [IsFFE and IsCoeffsModConwayPolRep], 
        function(x)
    Print(DisplayString(x));
end);

InstallMethod(ViewString,"For large finite field elements",
        [IsFFE and IsCoeffsModConwayPolRep], 
        function(x)
    local   s;
    s := DisplayStringForLargeFiniteFieldElements(x);
    if Length(s) > ViewLength()*SizeScreen()[1] then
        return Concatenation("<<an element of GF(",
                       String(Characteristic(x)), ", ",
                       String(DegreeFFE(x)),")>>");
    else
        Remove(s); # get rid of trailing newline
        return s;
    fi;
end);

InstallMethod(ViewObj, "For large finite field elements",
        [IsFFE and IsCoeffsModConwayPolRep], 
        function(x)
    Print(ViewString(x));
end);

#############################################################################
##
#F FFECONWAY.GetConwayPolCoeffs( <family>, <degree>)
##
## returns stored Conway Polynomial coefficients from family
## triggers computation if needed.
##
FFECONWAY.GetConwayPolCoeffs := function(f,d)
    local   p;
    if not IsBound(f!.ConwayPolCoeffs) then
        f!.ConwayPolCoeffs := [];
    fi;
    if not IsBound(f!.ConwayPolCoeffs[d]) then
        p := f!.Characteristic;
        FFECONWAY.SetUpConwayStuff(p,d);
    fi;
    return f!.ConwayPolCoeffs[d];
end;
        
        
                 

#############################################################################
##
#F FFECONWAY.FiniteFieldEmbeddingRecord(<prime>, <smalldeg>, <bigdeg> )
##
## returns a record (stored in the family after it is first computed)
## describing the embedding of F1 = GF(p^d1) into F2= GF(p^d2). The components 
## of this record are:
## 
## mat: a <d1> x <d2> matrix whose rows are the canonical basis of F1
## semi: a semi-echelonized version of mat
## convert: a <d1> x <d1> matrix such that <convert>*<mat> = <semi>
## pivots: a vector giving the position of the first non-zero entry in each
##         row of <semi>
##



FFECONWAY.FiniteFieldEmbeddingRecord := function(p, d1,d2)
    local   fam,  c,  n,  zz,  x,  z1,  m,  z,  i,  r,  res;
    fam := FFEFamily(p);
    if not IsBound(fam!.embeddingRecords) then
        fam!.embeddingRecords := [];
    fi;
    if not IsBound(fam!.embeddingRecords[d2]) then
        fam!.embeddingRecords[d2] := [];
    fi;
    if not IsBound(fam!.embeddingRecords[d2][d1]) then
        c := FFECONWAY.GetConwayPolCoeffs(fam,d2);
        n := (p^d2-1)/(p^d1-1);
        zz := 0*Z(p);
        x := [zz,Z(p)^0];
        ConvertToVectorRep(x,p);
        z1 := PowerModCoeffs(x,n,c);
        fam!.ConwayFldEltReducers[d2](z1);
        m := [ZeroMutable(z1),z1];
        m[1][1] := Z(p)^0;
        z := z1;
        for i in [2..d1-1] do
            z := ProductCoeffs(z,z1);
            fam!.ConwayFldEltReducers[d2](z);
            Add(m,z);
        od;
        ConvertToMatrixRep(m,p);
        r := rec( mat := m);
        res := SemiEchelonMatTransformation(r.mat);
        r.semi := res.vectors;
        r.convert := res.coeffs;
        r.pivots := [];
        for i in [1..Length(res.heads)] do
            if res.heads[i] > 0 then
                r.pivots[res.heads[i]] := i;
            fi;
        od;
        Assert(2,d1 = 1 or res.relations = []);
        fam!.embeddingRecords[d2][d1] := r;
    fi;
    return fam!.embeddingRecords[d2][d1];
end;

#############################################################################
##
#F FFECONWAY.WriteOverLargerField( <ffe>, <bigdeg> )
##
## returns an element written over a field of degree <bigdeg>, but equal to <ffe>
## <ffe> can be an internal FFE or a ZmodpZ object
##

FFECONWAY.WriteOverLargerField := function(x,d2)
    local   fam,  p,  d1,  v,  f, y;
    fam := FamilyObj(x);
    p := fam!.Characteristic;
    if p^d2 <= MAXSIZE_GF_INTERNAL then
        return x;
    fi;
    if not IsCoeffsModConwayPolRep(x) then
        d1 := DegreeFFE(x);
        if d1 = d2 then
            return x;
        fi;
        v := Coefficients(CanonicalBasis(AsField(GF(p,1),GF(p,d1))),x);
    else
        d1 := x![2];
        if d1 = d2 then
            return x;
        fi;
        v := x![1];
    fi;
    Assert(1,d2 mod d1 = 0);
    f := FFECONWAY.FiniteFieldEmbeddingRecord(p,d1,d2);
    if not IsCoeffsModConwayPolRep(x) or x![3] = false then
        y := x;
    elif x![3] <> fail then
        y := x![3];
    else
        y := fail;
    fi;
    return Objectify(fam!.ConwayFldEltDefaultType, [v*f!.mat,d2,y]);
end;

#############################################################################
##
#F FFECONWAY.TryToWriteInSmallerField( <ffe>, <smalldeg> )
##
## returns an element written over a field of degree <smalldeg>, but equal to <ffe>
## if possibe, otherwise fail. The returned element may be an internal FFE
## or a ZmodpZ object.
##

FFECONWAY.TryToWriteInSmallerField := function(x,d1)
    local   dmin,  fam,  p,  d2,  smalld,  r,  v,  v2,  i,  piv,  w,  
            oversmalld,  z;
    if IsInternalRep(x) then
        return fail;
    fi;
    if IsZmodpZObj(x) then
        return fail;
    fi;
    if d1 = x![2] then
        return fail;
    fi;
    if x![3] = false then
        return fail;
    fi;
    if x![3] <> fail then
        if IsCoeffsModConwayPolRep(x![3]) then
            dmin := x![3]![2];
        else
            dmin := DegreeFFE(x![3]);
        fi;
        if dmin = d1 then
            return x![3];
        elif d1 mod dmin = 0 then
            return FFECONWAY.WriteOverLargerField(x![3],d1);
        else
            return fail;
        fi;
    fi;
    fam := FamilyObj(x);
    p := fam!.Characteristic;
    d2 := x![2];
    if not IsMutable(x![1]) then
        x![1] := ShallowCopy(x![1]);
    fi;
    PadCoeffs(x![1],d2);
    smalld := Gcd(d1,d2);
    r := FFECONWAY.FiniteFieldEmbeddingRecord(p, smalld,d2);
    v := ShallowCopy(x![1]);
    v2 := ZeroMutable(r.convert[1]);
    for i in [1..smalld] do
        piv := r.pivots[i];
        w := r.semi[i];
        x := v[piv]/w[piv];
        AddCoeffs(v,w,-x);
        AddCoeffs(v2,r.convert[i],x);
    od;
    if not IsZero(v) then
        return fail;
    fi;
    if d1 = 1 then
        oversmalld :=  v2[1];
    elif p^d1 <= MAXSIZE_GF_INTERNAL then
        z := Z(p^smalld);
        oversmalld :=  Sum([1..smalld], i-> z^(i-1)*v2[i]);
        
    else
        oversmalld :=  Objectify(fam!.ConwayFldEltDefaultType,[v2,d1,fail]);
    fi;
    if smalld < d1 then
        return FFECONWAY.WriteOverLargerField(oversmalld, d1);
    else
       return oversmalld;   
    fi;
end;

#############################################################################
##
#F FFECONWAY.WriteOverSmallestField( <ffe> )
## 
## Returns <ffe> written over the field it generates.
##

FFECONWAY.WriteOverSmallestField := function(x)
    local   d,  f,  fac,  l,  d1,  x1,  x2;
    if IsInternalRep(x) or IsZmodpZObj(x) then
        return x;
    fi;
    if x![3] = false then
        return x;
    elif x![3] <> fail then
        return x![3];
    fi;
    d := x![2];
    f := Collected(FactorsInt(d));
    for fac in f do
        l := fac[1];
        d1 := d/l;
        x1 := FFECONWAY.TryToWriteInSmallerField(x,d1);
        if x1 <> fail then
            x2 := FFECONWAY.WriteOverSmallestField(x1);
            x![3] := x2;
            return x2;
        fi;
    od;
    x![3] := false;
    return x;
end;

#############################################################################
##
#M DegreeFFE( <ffe> )

InstallMethod(DegreeFFE, [IsCoeffsModConwayPolRep and IsFFE],
        function(x)
    local   y;
    y := FFECONWAY.WriteOverSmallestField(x);
    if  IsCoeffsModConwayPolRep(y)  then
        return y![2];
    else
        return DegreeFFE(y);
    fi;
end);

#############################################################################
##
#M  \=(<ffe>,<ffe>)
##
## Includes equality with internal FFE and ZmodpZ objects
##

InstallMethod(\=, 
        IsIdenticalObj, 
        [IsCoeffsModConwayPolRep and IsFFE, IsCoeffsModConwayPolRep and IsFFE],
        function(x1,x2)
    local   d1,  d2,  y2,  y1,  d;
    d1 := x1![2];
    d2 := x2![2];
    if d1 = d2 then
        return x1![1] = x2![1];
    fi;
    if d2 mod d1 = 0 then
        y2 := FFECONWAY.TryToWriteInSmallerField(x2,d1);
        if y2 = fail then
            return false;
        else 
            return y2![1] = x1![1];
        fi;
    elif d1 mod d2 = 0 then
        y1 := FFECONWAY.TryToWriteInSmallerField(x1,d2);
        if y1 = fail then
            return false;
        else 
            return y1![1] = x2![1];
        fi;
    else
        d := Gcd(d1,d2);
        y1 := FFECONWAY.TryToWriteInSmallerField(x1,d);
        if y1 = fail then
            return false;
        fi;
        y2 := FFECONWAY.TryToWriteInSmallerField(x2,d);
        if y2 = fail then
            return false;
        fi;
        return y1 = y2;
    fi;
end);


InstallMethod(\=, 
        IsIdenticalObj, 
        [IsCoeffsModConwayPolRep and IsFFE, IsFFE],
        function(x1,x2)
    local   d2,  y1;
    d2 := DegreeFFE(x2);
    y1 := FFECONWAY.TryToWriteInSmallerField(x1,d2);
    if y1 = fail then
        return false;
    else
        return y1 = x2;
    fi;
end);

InstallMethod(\=, 
        IsIdenticalObj, 
        [ IsFFE, IsCoeffsModConwayPolRep and IsFFE],
        function(x1,x2)
    local   d1,  y2;
    d1 := DegreeFFE(x1);
    y2 := FFECONWAY.TryToWriteInSmallerField(x2,d1);
    if y2 = fail then
        return false;
    else
        return y2 = x1;
    fi;
end);

#############################################################################
##
#F FFECONWAY.CoeffsOverCommonField(<ffe>,<ffe>) .. utility function
##
## Returns a length 3 list. The first and second entries of the
## list are the coefficient vectors of the two arguments written over
## a field which contains both of them, whose degree is the third entry
##
FFECONWAY.CoeffsOverCommonField := function(x1,x2)
    local   fam,  d1,  d2,  v1,  v2,  d,  y2,  y1;
    fam := FamilyObj(x1);
    if IsCoeffsModConwayPolRep(x1) then
        d1 := x1![2];
        v1 := x1![1];
    else
        d1 := DegreeFFE(x1);
    fi;
    if IsCoeffsModConwayPolRep(x2) then
        d2 := x2![2];
        v2 := x2![1];
    else
        d2 := DegreeFFE(x2);
    fi;
    if d1 = d2 then
        d := d1;
    elif d1 mod d2 = 0 then
        y2 := FFECONWAY.WriteOverLargerField(x2,d1);
        v2 := y2![1];
        d := d1;
    elif d2 mod d1 = 0 then
        y1 := FFECONWAY.WriteOverLargerField(x1,d2);
        v1 := y1![1];
        d := d2;
    else
        d := Lcm(d1,d2);
        Z(Characteristic(fam),d);
        y1 := FFECONWAY.WriteOverLargerField(x1,d);
        v1 := y1![1];
        y2 := FFECONWAY.WriteOverLargerField(x2,d);
        v2 := y2![1];
    fi;
    return [v1,v2,d];
end;

#############################################################################
##
#F FFECONWAY.SumConwayOtherFFEs( <ffe1>, <ffe2> ) .. Sum method
##   this is the sum method for cases where one of the summands might
##   not be in the Conway field representation.
##

FFECONWAY.SumConwayOtherFFEs := function(x1,x2)
    local   fam,  cc,  v;
    fam := FamilyObj(x1);
    cc := FFECONWAY.CoeffsOverCommonField(x1,x2);
    v := cc[1]+cc[2];
       return Objectify(fam!.ConwayFldEltDefaultType, [v,cc[3],fail]);
end;

#############################################################################
##
#M \+(<ffe1>,<ffe2>) 
##
## try and be quick in the common case of two Conway elements over the same field.
## also handle all other cases.

InstallMethod(\+,
        IsIdenticalObj,
        [ IsCoeffsModConwayPolRep and IsFFE, 
          IsCoeffsModConwayPolRep and IsFFE],
        function(x1,x2)
    local   v,  d,  cc,  fam;
    if x1![2] = x2![2] then
        v := x1![1]+x2![1];
        d := x1![2];
    else
        cc := FFECONWAY.CoeffsOverCommonField(x1,x2);
        v := cc[1]+cc[2];
        d := cc[3];
    fi;
    fam := FamilyObj(x1);
    return Objectify(fam!.ConwayFldEltDefaultType, 
                   [v,d,fail]);
end);

InstallMethod(\+,
        IsIdenticalObj,
        [ IsCoeffsModConwayPolRep and IsFFE, 
          IsFFE],
        FFECONWAY.SumConwayOtherFFEs
        );

InstallMethod(\+,
        IsIdenticalObj,
        [ IsFFE, 
          IsCoeffsModConwayPolRep and IsFFE],
        FFECONWAY.SumConwayOtherFFEs
        );

InstallMethod(SUM_FFE_LARGE,
        IsIdenticalObj,
        [ IsFFE and IsInternalRep,
          IsFFE and IsInternalRep],
        FFECONWAY.SumConwayOtherFFEs);

FFECONWAY.CATCH_UNEQUAL_CHARACTERISTIC := function(x,y)
    if Characteristic(x) <> Characteristic(y) then
        Error("Binary operation on finite field elements: characteristics must match\n");
    fi;
    TryNextMethod();
end;

InstallMethod(\+, [IsFFE,IsFFE],
        FFECONWAY.CATCH_UNEQUAL_CHARACTERISTIC);

#############################################################################
##
#F FFECONWAY.DiffConwayOtherFFEs( <ffe1>, <ffe2> ) .. Sum method
##   this is the sum method for cases where one of the summands might
##   not be in the Conway field representation.
##

FFECONWAY.DiffConwayOtherFFEs := function(x1,x2)
    local   fam,  cc,  v;
    fam := FamilyObj(x1);
    cc := FFECONWAY.CoeffsOverCommonField(x1,x2);
    v := cc[1]-cc[2];
       return Objectify(fam!.ConwayFldEltDefaultType, [v,cc[3],fail]);
end;

#############################################################################
##
#M \-(<ffe1>,<ffe2>) 
##
## try and be quick in the common case of two Conway elements over the same field.
## also handle all other cases.

InstallMethod(\-,
        IsIdenticalObj,
        [ IsCoeffsModConwayPolRep and IsFFE, 
          IsCoeffsModConwayPolRep and IsFFE],
        function(x1,x2)
    local   v,  d,  cc,  fam;
    if x1![2] = x2![2] then
        v := x1![1]-x2![1];
        d := x1![2];
    else
        cc := FFECONWAY.CoeffsOverCommonField(x1,x2);
        v := cc[1]-cc[2];
        d := cc[3];
    fi;
    fam := FamilyObj(x1);
    return Objectify(fam!.ConwayFldEltDefaultType, 
                   [v,d,fail]);
end);

InstallMethod(\-,
        IsIdenticalObj,
        [ IsCoeffsModConwayPolRep and IsFFE, 
          IsFFE],
        FFECONWAY.DiffConwayOtherFFEs
        );

InstallMethod(\-,
        IsIdenticalObj,
        [ IsFFE, 
          IsCoeffsModConwayPolRep and IsFFE],
        FFECONWAY.DiffConwayOtherFFEs
        );

InstallMethod(DIFF_FFE_LARGE,
        IsIdenticalObj,
        [ IsFFE and IsInternalRep,
          IsFFE and IsInternalRep],
        FFECONWAY.DiffConwayOtherFFEs);

InstallMethod(\-, [IsFFE,IsFFE],
        FFECONWAY.CATCH_UNEQUAL_CHARACTERISTIC);


#############################################################################
##
#F FFECONWAY.ProdConwayOtherFFEs(<ffe1>,<ffe2>) general product method
##

FFECONWAY.ProdConwayOtherFFEs := function(x1,x2)
    local   fam,  cc,  v,  c;
    fam := FamilyObj(x1);
    cc := FFECONWAY.CoeffsOverCommonField(x1,x2);
    v := ProductCoeffs(cc[1],cc[2]);
    fam!.ConwayFldEltReducers[cc[3]](v);
    return Objectify(fam!.ConwayFldEltDefaultType, [v,cc[3], fail]);
end;

#############################################################################
##
#M \*(<ffe1>, <ffe2>) 

InstallMethod(\*,
        IsIdenticalObj,
                [ IsCoeffsModConwayPolRep and IsFFE, 
                  IsCoeffsModConwayPolRep and IsFFE],
        function(x1,x2)
    local   v,  d,  cc,  fam;
    if x1![2] = x2![2] then
        v := ProductCoeffs(x1![1],x2![1]);
        d := x1![2];
    else
        cc := FFECONWAY.CoeffsOverCommonField(x1,x2);
        v := ProductCoeffs(cc[1],cc[2]);
        d := cc[3];
    fi;
    fam := FamilyObj(x1);
    fam!.ConwayFldEltReducers[d](v);
    return Objectify(fam!.ConwayFldEltDefaultType, 
                   [v,d,fail]);
    end

);

InstallMethod(\*,
        IsIdenticalObj,
                [ IsFFE, 
                  IsCoeffsModConwayPolRep and IsFFE],
        FFECONWAY.ProdConwayOtherFFEs
);
InstallMethod(\*,
        IsIdenticalObj,
                [ IsCoeffsModConwayPolRep and IsFFE,
                  IsFFE ],
        FFECONWAY.ProdConwayOtherFFEs
);

InstallMethod(PROD_FFE_LARGE,
        IsIdenticalObj,
        [ IsFFE and IsInternalRep,
          IsFFE and IsInternalRep],
        FFECONWAY.ProdConwayOtherFFEs);

InstallMethod(\*, [IsFFE,IsFFE],
        FFECONWAY.CATCH_UNEQUAL_CHARACTERISTIC);

InstallMethod(QUO, [IsFFE,IsFFE],
        FFECONWAY.CATCH_UNEQUAL_CHARACTERISTIC);


#############################################################################
##
#M AdditiveInverse

InstallMethod(AdditiveInverseOp,
        [ IsCoeffsModConwayPolRep and IsFFE],
        function(x)
    local   fam, y;
    fam := FamilyObj(x);
    if IsBool(x![3]) then
        y := x![3];
    else
        y := -x![3];
    fi;
    return Objectify(fam!.ConwayFldEltDefaultType, [AdditiveInverseMutable(x![1]),x![2],y]);
end);

#############################################################################
##
#M Inverse -- uses Euclids algorithm to express the GCD of x and the ConwayPolynomial
## (which had better be 1!) as r.x + s.c (actually don't compute s). Then r is
## the inverse of x.
##

InstallMethod(InverseOp, 
        [ IsCoeffsModConwayPolRep and IsFFE],
        function(x)
    local   t, fam,  p,  d,  c,  a,  b,  r,  s,  qr, y;
    fam := FamilyObj(x);
    p := fam!.Characteristic;
    d := x![2];
    c := FFECONWAY.GetConwayPolCoeffs(fam,d);
    a := ShallowCopy(x![1]);
    b := ShallowCopy(c);
    r := [Z(p)^0];
    ConvertToVectorRep(r,p);
    s := ZeroMutable(r);
    ShrinkRowVector(a);
    if Length(a) = 0 then
        return fail;
    fi;
    while Length(a) > 1 do
        
        qr := QuotRemCoeffs(b,a);
        b := a;
        a := qr[2];
        ShrinkRowVector(a);
        t := r;
        r := s-ProductCoeffs(r,qr[1]);
        s := t;
    od;
    Assert(1,Length(a) = 1);
    MultRowVector(r,Inverse(a[1]));
    if AssertionLevel() >= 2 then
        t := ProductCoeffs(x![1],r);
        fam!.ConwayFldEltReducers[d](t);
        if not IsOne(t[1]) or ForAny([2..Length(t)], i->not IsZero(t[i])) then
            Error("Inverse has failed");
        fi;
    fi;
    fam!.ConwayFldEltReducers[d](r);
    if IsBool(x![3]) then
        y := x![3];
    else
        y := Inverse(x![3]);
    fi;
    return Objectify(fam!.ConwayFldEltDefaultType,[r,d,y]);
end);

InstallMethod(QUO_FFE_LARGE,
        IsIdenticalObj,
        [ IsFFE and IsInternalRep,
          IsFFE and IsInternalRep],
        function(x,y)
    return FFECONWAY.ProdConwayOtherFFEs(x,y^-1);
end);



#############################################################################
##
#M IsZero
##

InstallMethod(IsZero, 
        [ IsCoeffsModConwayPolRep and IsFFE],
        x-> IsZero(x![1]));

#############################################################################
##
#M IsOne -- coefficients vector must be [1,0,..0]
##


InstallMethod(IsOne,
        [ IsCoeffsModConwayPolRep and IsFFE],
        function(x) 
    local   v,  i;
    v := x![1];
    if not IsOne(v[1]) then
        return false;
    fi;
    for i in [2..Length(v)] do
        if not IsZero(v![i]) then
            return false;
        fi;
    od;
    return true;
end);

#############################################################################
##
#M  ZeroOp -- Make a zero.
##

FFECONWAY.Zero := function(x)
    local   fam,  d;
    fam := FamilyObj(x);
    if not IsBound(fam!.ZeroConwayFFEs) then
        fam!.ZeroConwayFFEs := [];
    fi;
    d := x![2];
    if not IsBound(fam!.ZeroConwayFFEs[d]) then
        fam!.ZeroConwayFFEs[d] := Objectify(fam!.ConwayFldEltDefaultType,[ZeroMutable(x![1]),d, 
                                          0*Z(fam!.Characteristic)]);
    fi;
    return fam!.ZeroConwayFFEs[d];
end;
        

InstallMethod(ZeroOp,
        [ IsCoeffsModConwayPolRep and IsFFE],
        FFECONWAY.Zero);

InstallMethod(ZeroAttr,
        [ IsCoeffsModConwayPolRep and IsFFE],
        FFECONWAY.Zero);



#############################################################################
##
#M OneOp 
##

FFECONWAY.One := function(x)
    local   fam,  d,  v;
    fam := FamilyObj(x);
    if not IsBound(fam!.OneConwayFFEs) then
        fam!.OneConwayFFEs := [];
    fi;
    d := x![2];
    if not IsBound(fam!.OneConwayFFEs[d]) then
        v := ZeroMutable(x![1]);
        v[1] := Z(fam!.Characteristic)^0;
        fam!.OneConwayFFEs[d] := Objectify(fam!.ConwayFldEltDefaultType,[v,d, 
                                         Z(fam!.Characteristic)^0]);
    fi;
    return fam!.OneConwayFFEs[d];
end;
        

InstallMethod(OneOp,
        [ IsCoeffsModConwayPolRep and IsFFE],
        FFECONWAY.One);

InstallMethod(OneAttr,
        [ IsCoeffsModConwayPolRep and IsFFE],
        FFECONWAY.One);


#############################################################################
##
#M \<   this is a bit complicated due to the rules for comparing FFEs in GAP
##       We have to identify the smallest field representation of our elements
##       then deal with the possibility that that is in another representation
##

InstallMethod(\<,
        IsIdenticalObj,
        [ IsCoeffsModConwayPolRep and IsLexOrderedFFE,
          IsCoeffsModConwayPolRep and IsLexOrderedFFE ],
        function(x1,x2)
    local   y1,  y2,  d1,  d2;
    y1 := FFECONWAY.WriteOverSmallestField(x1);
    y2 := FFECONWAY.WriteOverSmallestField(x2);
    if IsInternalRep(y1) then
        if IsInternalRep(y2) then
            return y1<y2;
        fi;
        return true;
    elif IsInternalRep(y2) then
        return false;
    fi;
    if IsModulusRep(y1) then
        if IsModulusRep(y2) then
            return y1<y2;
        fi;
        return true;
    elif IsModulusRep(y2) then
        return false;
    fi;
    
    d1 := y1![2];
    d2 := y2![2];
    if d1 < d2 then
        return true;
    elif d1 > d2 then
        return false;
    fi;
    return y1![1] < y2![1];
end);
        

InstallMethod(\<,
        IsIdenticalObj,
        [ IsCoeffsModConwayPolRep,
          IsFFE and IsInternalRep ],
        function(x1,x2)
    local   y1;
    y1 := FFECONWAY.WriteOverSmallestField(x1);
    if not IsInternalRep(y1) then
        return false;
    else
        return y1 < x2;
    fi;
end);

InstallMethod(\<,
        IsIdenticalObj,
        [ IsFFE and IsInternalRep,
          IsCoeffsModConwayPolRep],

        function(x1,x2)
    local   y2;
    y2 := FFECONWAY.WriteOverSmallestField(x2);
    if not IsInternalRep(y2) then
        return true;
    else
        return x1 < y2;
    fi;
end);

InstallMethod(\<,
        IsIdenticalObj,
        [ IsCoeffsModConwayPolRep,
          IsFFE and IsModulusRep ],
        function(x1,x2)
    local   y1;
    y1 := FFECONWAY.WriteOverSmallestField(x1);
    if not IsModulusRep(y1) then
        return false;
    else
        return y1 < x2;
    fi;
end);

InstallMethod(\<,
        IsIdenticalObj,
        [ IsFFE and IsModulusRep,
          IsCoeffsModConwayPolRep],

        function(x1,x2)
    local   y2;
    y2 := FFECONWAY.WriteOverSmallestField(x2);
    if not IsModulusRep(y2) then
        return true;
    else
        return x1 < y2;
    fi;
end);

#############################################################################
##
#M  IntFFE
##
        
InstallMethod(IntFFE,
        [IsFFE and IsCoeffsModConwayPolRep],
        function(x)
    local   i;
    for i in [2..Length(x![1])] do
        if not IsZero(x![1][i]) then
            Error("IntFFE: element must lie in prime field");
        fi;
    od;
    return IntFFE(x![1][1]);
end);

#############################################################################
##
#M LogFFE 
##

#
# Adapted from the integer code by AH and Sean Gage
#


FFECONWAY.LogFFERhoIterate := function(y,z,q)
    local   p,  p3,  zp3,  k,  x,  xd,  a,  ad,  b,  bd,  n,  nd,  m,  
            r;
    p := Characteristic(y);
    p3:=QuoInt(q,3);
    zp3:=QuoInt(2*q,3);
    k := q-1;
    x := One(y);
    xd := One(y);
    a := 0;
    ad := 0;
    b := 0;
    bd := 0;
    repeat
        if not IsCoeffsModConwayPolRep(x) then
            n := 0; 
        else
            n := NumberFFVector(x![1],p);
        fi;
        if n < p3 then
            x := x * y;
            a := (a + 1) mod k;
        elif n < zp3 then
            x := x * x;
            a := (a*2) mod k;
            b := (b*2) mod k;
        else
            x := x * z;
            b := (b + 1) mod k;
        fi;
        
        if not IsCoeffsModConwayPolRep(xd) then
            nd := 0; 
        else
            nd := NumberFFVector(xd![1],p);
        fi;
        if nd <p3 then
            xd := xd * y;
            ad := (ad + 1) mod k;
        elif nd < zp3 then
            xd := xd * xd;
            ad := (ad*2) mod k;
            bd := (bd*2) mod k;
        else
            xd := xd * z;
            bd := (bd + 1) mod k;
        fi;
        if not IsCoeffsModConwayPolRep(xd) then
            nd := 0; 
        else
            nd := NumberFFVector(xd![1],p);
        fi;
        if nd <p3 then
            xd := xd * y;
            ad := (ad + 1) mod k;
        elif nd < zp3 then
            xd := xd * xd;
            ad := (ad*2) mod k;
            bd := (bd*2) mod k;
        else
            xd := xd * z;
            bd := (bd + 1) mod k;
        fi;
  until x=xd;

  m := (a-ad) mod k;
 r := (bd-b) mod k;
  return [m,r];
end;



FFECONWAY.DoLogFFERho :=function(y,z,ord,f,q)
    local   fact,  s,  i,  t,  d,  Q,  R,  MN,  M,  N,  rep,  k,  
            theta,  Qp,  o;
    fact:=[];
    s:=ord;
    for i in f do
        t:=s/i;
        if IsInt(t) then
            s:=t;
            Add(fact,i);
        fi;
    od;

    if Length(fact)>1 then
        d:=ord;
        while (d=ord) and Length(fact)>0 do
            s:=Remove(fact);
            t:=ord/s;
            Q:=y^s;
            R:=z^s;
            
        # iterate
            MN:=FFECONWAY.LogFFERhoIterate(Q,R,q);
            M:=MN[1];
            N:=MN[2];
            rep:=GcdRepresentation(ord,s*M);
            d:=rep[1]*ord+rep[2]*s*M;
        od;
        
        if d < ord then
            k:=(rep[2]*s*N/d);
            if Gcd(DenominatorRat(k),ord)<>1 then
                return fail;        # can't invert (can't happen if not primitive root)
            fi;
            k:=k mod ord;
            theta:= z^(ord/d);
            
            Qp:=y/(z^k);
            i:=FFECONWAY.DoLogFFERho(Qp,theta,d,f,q);
            if i=fail then return i;fi; # bail out
            o:=(k+i*(ord/d)) mod ord;
            Assert(1,z^o=y);
            return o;
        fi;
    fi;
    
    # naive case, iterate
    MN:=FFECONWAY.LogFFERhoIterate(y,z,q);
    M:=MN[1];
    N:=MN[2];
    rep:=GcdRepresentation(ord,M);
    d:=rep[1]*ord+rep[2]*M;
    k:=(rep[2]*N/d);
    if Gcd(DenominatorRat(k),ord)<>1 then
        return fail;        # can't invert (can't happen if not primitive root)
    fi;
    k:=k mod ord;
    theta:= z^(ord/d);
    Qp:= y/(z^k);
    i := 0; while i < d do i := i + 1;
        if IsOne(Qp) then
            Assert(1,z^k = y);
            return k;
        fi;
        k:=(k+ord/d) mod ord;
        Qp:=Qp/theta;
    od;
    # process failed (because z was not a primitive root)
    return fail;
end;

FFECONWAY.DoLogFFE := 
        function(y,z)
    local   d,  p,  q,  dy,  o,  ix,  f;
    if IsZero(z)  then
        Error("LogFFE: element is not a power of base");
    fi;       
    #
    # Reduce to smallest possible fields.
    #
    
    y := FFECONWAY.WriteOverSmallestField(y);
    z := FFECONWAY.WriteOverSmallestField(z);
    
    #
    # If we're in the Zech range then all is good
    #
    if IsInternalRep(z) then
        if not IsInternalRep(y) then
            Error("LogFFE: element is not a power of base");
        else
            return LogFFE(y,z);
        fi;
    fi;
    
    
    d := DegreeFFE(z);
    p := Characteristic(z);
    q := p^d;
    dy := DegreeFFE(y);
    
    if  d mod dy <> 0  then
        Error("LogFFE: element is not a power of base");
    fi;
    
    #
    # If elements are not over same field then I can find the smallest power of z
    # that lies in the right field and recurse. This handles the case that y is in internal rep
    #
    if d <> dy then
        o := Order(z);
        ix := o/Gcd(o,p^dy-1);
        return LogFFE(y,z^ix)*ix;
    fi;
    
    # use rho method
    f:=FactorsInt(q-1:quiet); # Quick factorization, don't stop if its too hard
     return FFECONWAY.DoLogFFERho(y,z,q-1,f,q);
 end;
 
InstallMethod( LogFFE,
        IsIdenticalObj,
        [IsFFE and IsCoeffsModConwayPolRep, IsFFE and IsCoeffsModConwayPolRep],
        FFECONWAY.DoLogFFE
        );


InstallMethod( LogFFE,
        IsIdenticalObj,
        [IsFFE and IsInternalRep, IsFFE and IsCoeffsModConwayPolRep],
        FFECONWAY.DoLogFFE
);

InstallMethod( LogFFE,
        IsIdenticalObj,
        [ IsFFE and IsCoeffsModConwayPolRep, IsFFE and IsInternalRep],
        FFECONWAY.DoLogFFE
);


#############################################################################
##
#M  Order -- multiplicative order of an FFE
##


InstallMethod( Order,
        [IsFFE],
        function(z)
    local   p,  d,  ord,  facs,  f,  i,  o;
    p := Characteristic(z);
    d := DegreeFFE(z);
    ord := p^d-1;
    facs := Collected(FactorsInt(ord));
    for f in facs do
        for i in [1..f[2]] do
            o := ord/f[1];
            if not IsOne(z^o) then
                break;
            fi;
            ord := o;
        od;
    od;
    return ord;
end);
    


#############################################################################
##
#M LargeGaloisField(p,d) -- construct GFs in this size range
##           try next method if it goes wrong, to avoid dependency on
##           method selection sequence.
##
##         Cache fields in the family. 
##         Assuming we came via GF we have already passed a cache for last case called
##

InstallMethod( LargeGaloisField,
        [IsPosInt, IsPosInt],
        function(p,d)
    local   fam;
    if not IsPrimeInt(p) then
        Error("LargeGaloisField: Characteristic must be prime");
    fi;
    if d =1 or p^d <= MAXSIZE_GF_INTERNAL then
        TryNextMethod();
    fi;
    fam := FFEFamily(p);
    if not IsBound(fam!.ConwayFieldCache) then
        fam!.ConwayFieldCache := [];
    fi;
    if not IsBound(fam!.ConwayFieldCache[d]) then
        fam!.ConwayFieldCache[d] := FieldByGenerators(GF(p,1),[FFECONWAY.ZNC(p,d)]);
    fi;
    return fam!.ConwayFieldCache[d];
end);
        

#############################################################################
##
#M  PrimitiveRoot for Galois fields
##

InstallMethod(PrimitiveRoot,
        [IsField and IsFFECollection and IsFinite],
        function(f)
    local   p,  d;
    p := Characteristic(f);
    d := DegreeOverPrimeField(f);
    if d > 1 and p^d > MAXSIZE_GF_INTERNAL then
        return FFECONWAY.ZNC(p,d);
    else
        TryNextMethod();
    fi;
end);
        
#############################################################################
##
#M Coefficients of an element wrt the canonical basis -- are stored in the 
##                                                       element
InstallMethod(Coefficients,
        "For a FFE in Conway polynomial represntation wrt the canonical basis of its natural field",
        IsCollsElms,
        [IsCanonicalBasis and IsBasisFiniteFieldRep, IsFFE and IsCoeffsModConwayPolRep],
        function(cb,x)
    if not IsPrimeField(LeftActingDomain(UnderlyingLeftModule(cb))) then
        TryNextMethod();
    fi;
    if DegreeOverPrimeField(UnderlyingLeftModule(cb)) <> x![2] then
        TryNextMethod();
    fi;
    PadCoeffs(x![1],x![2]);
    return Immutable(x![1]);
end);

#############################################################################
##
#M Enumerator -- for a GF -- use an Enumerator for the equivalent rowspace
##
## when looking up elements, we may have to promote them to the right field

InstallMethod(Enumerator,
        [IsField and IsFinite and IsFFECollection],
        function(f)
    local   p,  fam,  d,  e,  x;
    if Size(f) <= MAXSIZE_GF_INTERNAL  then
        TryNextMethod();
    fi;
    p := Characteristic(f);
    fam := FFEFamily(p);
    d := DegreeOverPrimeField(f);
    if d = 1 then TryNextMethod(); fi;
    e := Enumerator(RowSpace(GF(p,1),d));
    return EnumeratorByFunctions(f, rec(
                   ElementNumber := function(en,n)
        return Objectify(fam!.ConwayFldEltDefaultType, [ e[n], d, fail]);
        end,
                   NumberElement := function(en,x)
        x := FFECONWAY.WriteOverLargerField(x,d);
        return Position(e,x![1]); 
    end));
end);

#############################################################################
##
#M  AsList, Iterator
##
##   since we have a really efficient Enumerator method, lets use it.
     
InstallMethod(AsList,
        [IsField and IsFinite and IsFFECollection],
        function(f)
    if Size(f) <= MAXSIZE_GF_INTERNAL  then
        TryNextMethod();
    fi;     
    return AsList(Enumerator(f));
end);

InstallMethod(Iterator, 
        [IsField and IsFinite and IsFFECollection],
        function(f)
    if Size(f) <= MAXSIZE_GF_INTERNAL  then
        TryNextMethod();
    fi;
    return IteratorList(Enumerator(f));
end);

#############################################################################
##
#M  Random -- use Rowspace
##

InstallMethod(Random, 
        [IsField and IsFFECollection and IsFinite],
        function(f)
    local   d,  p,  v,  fam;
    if Size(f) <= MAXSIZE_GF_INTERNAL then
        TryNextMethod();
    fi;
    if IsPrimeField(f) then
        TryNextMethod();
    fi;
    d := DegreeOverPrimeField(f);
    p := Characteristic(f);
    v := Random(RowSpace(GF(p,1),d));
    fam := FFEFamily(Characteristic(f));
    return Objectify(fam!.ConwayFldEltDefaultType, [v,d,fail]);
end);

#############################################################################
##
#M  MinimalPolynomial(<fld>,<elm>,<ind>)
##

InstallMethod(MinimalPolynomial, 
        IsCollsElmsX,
        [IsPrimeField, IsCoeffsModConwayPolRep and IsFFE, IsPosInt],
        function(fld, elm, ind)
    local   fam,  d,  dd,  x,  y,  p,  o,  m,  i,  r;
    fam := FamilyObj(elm);
    d := DegreeFFE(elm);
    dd := elm![2];
    x := elm![1];
    y := x;
    p := Characteristic(elm);
    o := ListWithIdenticalEntries(dd,Z(p)*0);
    o[1] := Z(p)^0;
    ConvertToVectorRep(o,p);
    m := [o,y];
    for i in [2..d] do
        y := ProductCoeffs(y,x);
        fam!.ConwayFldEltReducers[dd](y);
        Add(m,y);
    od;
    ConvertToMatrixRep(m,p);
    r := SemiEchelonMatTransformation(m);
    Assert(1, Length(r.relations) = 1);
    return UnivariatePolynomialByCoefficients(fam, r.relations[1],ind);
end);
    


#############################################################################
##
#M  Display for matrix of ffes
##

InstallMethod( Display,
    "for matrix of FFEs (for larger fields)",
    [ IsFFECollColl and IsMatrix ], 10, # prefer this to existing method
        function(m)
    local   deg,  chr,  zero,  d,  w,  r,  dr,  x,  s,  y,  j,  a;
    if Length(m) = 0 or Length(m[1])= 0 then
        TryNextMethod();
    fi;
    deg  := Lcm( List( m, DegreeFFE ) );
    chr  := Characteristic(m[1][1]);
    if deg = 1 or chr^deg <= MAXSIZE_GF_INTERNAL then
        TryNextMethod();
    fi;
    zero := Zero(m[1][1]);
    Print("z = Z( ",chr,", ",deg,"); z2 = z^2, etc.\n");
    d := [];
    w := 1;
    for r in m do
        dr := [];
        for x in r do
            if IsZero(x) then
                Add(dr,".");
            else
                s := "";
                y := FFECONWAY.WriteOverLargerField(x,deg);
                for j in [0..deg-1] do
                    a := IntFFE(y![1][j+1]);
                    if a <> 0 then
                        if Length(s) <> 0 then
                            Append(s,"+");
                        fi;
                        if a = 1 and j = 0 then
                            Append(s,"1");
                        else
                            if a <> 1 then
                                Append(s,String(a));
                            fi;
                            if j <> 0 then
                                Append(s,"z");
                                if j <> 1 then
                                    Append(s,String(j));
                                fi;
                            fi;
                        fi;
                    fi;
                od;
                Add(dr,s);
                if Length(s) > w then
                    w := Length(s);
                fi;
            fi;
        od;
        Add(d,dr);
    od;
    for dr in d do
        for s in dr do
            Print(String(s,-w-1));
        od;
        Print("\n");
    od;
end);

#############################################################################
##
#F  FFECONWAY.WriteOverSmallestCommonField( <v> )
##

FFECONWAY.WriteOverSmallestCommonField := function(v)
    local   d,  degs,  p,  x,  dx,  i;
    d := 1;
    degs := [];
    p := Characteristic(v[1]);
    for x in v do
        if not IsFFE(x) or Characteristic(x) <> p then
            return fail;
        fi;
        dx := DegreeFFE(x);
        Add(degs, dx);
    od;
    d := Lcm(Set(degs));
    for i in [1..Length(v)] do
        if IsCoeffsModConwayPolRep(v[i]) then
            if d < v[i]![2] then
                v[i] := FFECONWAY.TryToWriteInSmallerField(v[i],d);
            elif d > v[i]![2] then
                v[i] := FFECONWAY.WriteOverLargerField(v[i],d);
            fi;
        fi;
    od;
    return p^d;
end;
        
#############################################################################
##
#M  AsInternalFFE( <conway ffe> )
##
InstallMethod( AsInternalFFE, [IsFFE and IsCoeffsModConwayPolRep],
        function (x)
    local y;
    y := FFECONWAY.WriteOverSmallestField(x);
    if IsInternalRep(y) then
        return y;
    else
        return fail;
    fi;
end);


SetNamesForFunctionsInRecord("FFECONWAY");
gap-libs 4r6p5-3 / usr / share / gap / lib / ffeconway.gi
