axiom-source 20170501-3 / usr / share / axiom-20170501 / src / algebra / FFCGP.spad

)abbrev domain FFCGP FiniteFieldCyclicGroupExtensionByPolynomial
++ Authors: J.Grabmeier, A.Scheerhorn
++ Date Created: 26.03.1991
++ Date Last Updated: 31 March 1991
++ References:
++ Grab92 Finite Fields in Axiom
++ Lidl83 Finite Field, Encyclopedia of Mathematics and Its Applications
++ Description:
++ FiniteFieldCyclicGroupExtensionByPolynomial(GF,defpol)  implements a
++ finite extension field of the ground field GF. Its elements are
++ represented by powers of a primitive element, a generator of the
++ multiplicative (cyclic) group. As primitive
++ element we choose the root of the extension polynomial defpol,
++ which MUST be primitive (user responsibility). Zech logarithms are stored
++ in a table of size half of the field size, and use \spadtype{SingleInteger}
++ for representing field elements, hence, there are restrictions
++ on the size of the field.

FiniteFieldCyclicGroupExtensionByPolynomial(GF,defpol) : SIG == CODE where
  GF    : FiniteFieldCategory                -- the ground field
  defpol: SparseUnivariatePolynomial GF      -- the extension polynomial
  -- the root of defpol is used as the primitive element

  PI  ==> PositiveInteger
  NNI ==> NonNegativeInteger
  I   ==> Integer
  SI  ==> SingleInteger
  SUP ==> SparseUnivariatePolynomial
  SAE ==> SimpleAlgebraicExtension(GF,SUP GF,defpol)
  V   ==> Vector GF
  FFP ==> FiniteFieldExtensionByPolynomial(GF,defpol)
  FFF ==> FiniteFieldFunctions(GF)
  OUT ==> OutputForm
  ARR ==> PrimitiveArray(SI)
  TBL ==> Table(PI,NNI)

  SIG ==> FiniteAlgebraicExtensionField(GF)  with

    getZechTable : () -> ARR
      ++ getZechTable() returns the zech logarithm table of the field
      ++ it is used to perform additions in the field quickly.

  CODE ==> add

-- global variables ===================================================

    Rep:= SI
    -- elements are represented by small integers in the range
    -- (-1)..(size()-2). The (-1) representing the field element zero,
    -- the other small integers representing the corresponding power
    -- of the primitive element, the root of the defining polynomial

    -- it would be very nice if we could use the representation
    -- Rep:= Union("zero", IntegerMod(size()$GF ** degree(defpol) -1)),
    -- why doesn't the compiler like this ?

    extdeg:NNI  :=degree(defpol)$(SUP GF)::NNI
    -- the extension degree

    sizeFF:NNI:=(size()$GF ** extdeg) pretend NNI
    -- the size of the field

    if sizeFF > 2**20 then
      error "field too large for this representation"

    sizeCG:SI:=(sizeFF - 1) pretend SI
    -- the order of the cyclic group

    sizeFG:SI:=(sizeCG quo (size()$GF-1)) pretend SI
    -- the order of the factor group

    zechlog:ARR:=new(((sizeFF+1) quo 2)::NNI,-1::SI)$ARR
    -- the table for the zech logarithm

    alpha :=new()$Symbol :: OutputForm
    -- get a new symbol for the output representation of
    -- the elements

    primEltGF:GF:=
      odd?(extdeg)$I => -$GF coefficient(defpol,0)$(SUP GF)
      coefficient(defpol,0)$(SUP GF)
    -- the corresponding primitive element of the groundfield
    -- equals the trace of the primitive element w.r.t. the groundfield

    facOfGroupSize := nil()$(List Record(factor:Integer,exponent:Integer))
    -- the factorization of sizeCG

    initzech?:Boolean:=true
    -- gets false after initialization of the zech logarithm array

    initelt?:Boolean:=true
    -- gets false after initialization of the normal element

    normalElt:SI:=0
    -- the global variable containing a normal element

-- functions ==========================================================

    -- for completeness we have to give a dummy implementation for
    -- 'tableForDiscreteLogarithm', although this function is not
    -- necessary in the cyclic group representation case

    tableForDiscreteLogarithm(fac) == table()$TBL

    getZechTable() == zechlog

    initializeZech:() -> Void

    initializeElt: () -> Void

    order(x:$):PI ==
      zero?(x) =>
        error"order: order of zero undefined"
      (sizeCG quo gcd(sizeCG,x pretend NNI))::PI

    primitive?(x:$) ==
      zero?(x) or (x = 1) => false
      gcd(x::Rep,sizeCG)$Rep = 1$Rep => true
      false

    coordinates(x:$) ==
      x=0 => new(extdeg,0)$(Vector GF)
      primElement:SAE:=convert(monomial(1,1)$(SUP GF))$SAE
      -- the primitive element in the corresponding algebraic extension
      coordinates(primElement **$SAE (x pretend SI))$SAE

    x:$ + y:$ ==
      if initzech? then initializeZech()
      zero? x => y
      zero? y => x
      d:Rep:=positiveRemainder(y -$Rep x,sizeCG)$Rep
      (d pretend SI) <= shift(sizeCG,-$SI (1$SI)) =>
        zechlog.(d pretend SI) =$SI -1::SI => 0
        addmod(x,zechlog.(d pretend SI) pretend Rep,sizeCG)$Rep
      --d:Rep:=positiveRemainder(x -$Rep y,sizeCG)$Rep
      d:Rep:=(sizeCG -$SI d)::Rep
      addmod(y,zechlog.(d pretend SI) pretend Rep,sizeCG)$Rep
      --positiveRemainder(x +$Rep zechlog.(d pretend SI) -$Rep d,sizeCG)$Rep

    initializeZech() ==
      zechlog:=createZechTable(defpol)$FFF
      -- set initialization flag
      initzech? := false
      void()$Void

    basis(n:PI) ==
      extensionDegree() rem n ^= 0 =>
        error("argument must divide extension degree")
      m:=sizeCG quo (size()$GF**n-1)
      [index((1+i*m) ::PI) for i in 0..(n-1)]::Vector $

    n:I * x:$ == ((n::GF)::$) * x

    minimalPolynomial(a) ==
      f:SUP $:=monomial(1,1)$(SUP $) - monomial(a,0)$(SUP $)
      u:$:=Frobenius(a)
      while not(u = a) repeat
        f:=f * (monomial(1,1)$(SUP $) - monomial(u,0)$(SUP $))
        u:=Frobenius(u)
      p:SUP GF:=0$(SUP GF)
      while not zero?(f)$(SUP $) repeat
        g:GF:=retract(leadingCoefficient(f)$(SUP $))
        p:=p+monomial(g,_
                      degree(f)$(SUP $))$(SUP GF)
        f:=reductum(f)$(SUP $)
      p

    factorsOfCyclicGroupSize() ==
      if empty? facOfGroupSize then initializeElt()
      facOfGroupSize

    representationType() == "cyclic"

    definingPolynomial() == defpol

    random() ==
      positiveRemainder(random()$Rep,sizeFF pretend Rep)$Rep -$Rep 1$Rep

    represents(v) ==
      u:FFP:=represents(v)$FFP
      u =$FFP 0$FFP => 0
      discreteLog(u)$FFP pretend Rep

    coerce(e:GF):$ ==
      zero?(e)$GF => 0
      log:I:=discreteLog(primEltGF,e)$GF::NNI *$I sizeFG
      -- version before 10.20.92: log pretend Rep
      -- 1$GF is coerced to sizeCG pretend Rep by old version
      -- now 1$GF is coerced to 0$Rep which is correct.
      positiveRemainder(log,sizeCG) pretend Rep

    retractIfCan(x:$) ==
      zero? x => 0$GF
      u:= (x::Rep) exquo$Rep (sizeFG pretend Rep)
      u = "failed" => "failed"
      primEltGF **$GF ((u::$) pretend SI)

    retract(x:$) ==
      a:=retractIfCan(x)
      a="failed" => error "element not in groundfield"
      a :: GF

    basis() == [index(i :: PI) for i in 1..extdeg]::Vector $

    inGroundField?(x) ==
      zero? x=> true
      positiveRemainder(x::Rep,sizeFG pretend Rep)$Rep =$Rep 0$Rep => true
      false

    discreteLog(b:$,x:$) ==
      zero? x => "failed"
      e:= extendedEuclidean(b,sizeCG,x)$Rep
      e = "failed" => "failed"
      e1:Record(coef1:$,coef2:$) := e :: Record(coef1:$,coef2:$)
      positiveRemainder(e1.coef1,sizeCG)$Rep pretend NNI

    - x:$ ==
        zero? x => 0
        characteristic() =$I 2 => x
        addmod(x,shift(sizeCG,-1)$SI pretend Rep,sizeCG)

    generator() == 1$SI
    createPrimitiveElement() == 1$SI
    primitiveElement() == 1$SI

    discreteLog(x:$) ==
      zero? x => error "discrete logarithm error"
      x pretend NNI

    normalElement() ==
      if initelt? then initializeElt()
      normalElt::$

    initializeElt() ==
      facOfGroupSize := factors(factor(sizeCG)$Integer)
      normalElt:=createNormalElement() pretend SI
      initelt?:=false
      void()$Void

    extensionDegree() == extdeg pretend PI

    characteristic() == characteristic()$GF

    lookup(x:$) ==
      x =$Rep (-$Rep 1$Rep) => sizeFF pretend PI
      (x +$Rep 1$Rep) pretend PI

    index(a:PI) ==
      positiveRemainder(a,sizeFF)$I pretend Rep -$Rep 1$Rep

    0 == (-$Rep 1$Rep)

    1 == 0$Rep

-- to get a "exponent like" output form
    coerce(x:$):OUT ==
      x =$Rep (-$Rep 1$Rep) => "0"::OUT
      x =$Rep 0$Rep => "1"::OUT
      y:I:=lookup(x)-1
      alpha **$OUT (y::OUT)

    x:$ = y:$ ==  x =$Rep y

    x:$ * y:$ ==
      x = 0 => 0
      y = 0 => 0
      addmod(x,y,sizeCG)$Rep

    a:GF * x:$ == coerce(a)@$ * x

    x:$/a:GF == x/coerce(a)@$

    inv(x:$)  ==
      zero?(x) => error "inv: not invertible"
      (x = 1) => 1
      sizeCG -$Rep x

    x:$ ** n:PI == x ** n::I

    x:$ ** n:NNI == x ** n::I

    x:$ ** n:I ==
      m:Rep:=positiveRemainder(n,sizeCG)$I pretend Rep
      m =$Rep 0$Rep => 1
      x = 0 => 0
      mulmod(m,x,sizeCG::Rep)$Rep