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

)abbrev domain FFP FiniteFieldExtensionByPolynomial
++ Authors: R.Sutor, J. Grabmeier, O. Gschnitzer, A. Scheerhorn
++ Date Created:
++ Date Last Updated: 31 March 1991
++ Reference:
++ Grab92 Finite Fields in Axiom
++ Lidl83 Finite Field, Encyclopedia of Mathematics and Its Applications
++ Description:
++ FiniteFieldExtensionByPolynomial(GF, defpol) implements the extension
++ of the finite field GF generated by the extension polynomial
++ defpol which MUST be irreducible.
++ Note: the user has the responsibility to ensure that
++ defpol is irreducible.

FiniteFieldExtensionByPolynomial(GF,defpol) : SIG == CODE where
  GF : FiniteFieldCategory
  defpol : SparseUnivariatePolynomial(GF)

  PI   ==> PositiveInteger
  NNI  ==> NonNegativeInteger
  SUP  ==> SparseUnivariatePolynomial
  I    ==> Integer
  R    ==> Record(key:PI,entry:NNI)
  TBL  ==> Table(PI,NNI)
  SAE  ==> SimpleAlgebraicExtension(GF,SUP GF,defpol)
  OUT  ==> OutputForm

  SIG ==> FiniteAlgebraicExtensionField(GF)

  CODE ==> add

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

    Rep:=SAE

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

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

    sizeCG:Integer := size()$GF**extdeg - 1
    -- the order of the multiplicative group

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

    normalElt:PI:=1
    -- for the lookup of the normal Element computed by
    -- createNormalElement

    primitiveElt:PI:=1
    -- for the lookup of the primitive Element computed by
    -- createPrimitiveElement()

    initlog?:Boolean:=true
    -- gets false after initialization of the discrete logarithm table

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

    discLogTable:Table(PI,TBL):=table()$Table(PI,TBL)
    -- tables indexed by the factors of sizeCG,
    -- discLogTable(factor) is a table  with keys
    -- primitiveElement() ** (i * (sizeCG quo factor)) and entries i for
    -- i in 0..n-1, n computed in initialize() in order to use
    -- the minimal size limit 'limit' optimal.

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

    generator() == reduce(monomial(1,1)$SUP(GF))$Rep

    norm x   == resultant(defpol, lift x)

    initializeElt: () -> Void

    initializeLog: () -> Void

    basis(n:PI) ==
      (extdeg rem n) ^= 0 => error "argument must divide extension degree"
      a:$:=norm(primitiveElement(),n)
      vector [a**i for i in 0..n-1]

    degree(x) ==
      y:$:=1
      m:=zero(extdeg,extdeg+1)$(Matrix GF)
      for i in 1..extdeg+1 repeat
        setColumn_!(m,i,coordinates(y))$(Matrix GF)
        y:=y*x
      rank(m)::PI

    minimalPolynomial(x:$) ==
      y:$:=1
      m:=zero(extdeg,extdeg+1)$(Matrix GF)
      for i in 1..extdeg+1 repeat
        setColumn_!(m,i,coordinates(y))$(Matrix GF)
        y:=y*x
      v:=first nullSpace(m)$(Matrix GF)
      +/[monomial(v.(i+1),i)$(SUP GF) for i in 0..extdeg]


    normal?(x) ==
      l:List List GF:=[entries coordinates x]
      a:=x
      for i in 2..extdeg repeat
        a:=Frobenius(a)
        l:=concat(l,entries coordinates a)$(List List GF)
      ((rank matrix(l)$(Matrix GF)) = extdeg::NNI) => true
      false

    a:GF * x:$ == a *$Rep x

    n:I * x:$ == n *$Rep x

    -x == -$Rep x

    random() == random()$Rep

    coordinates(x:$) == coordinates(x)$Rep

    represents(v) == represents(v)$Rep

    coerce(x:GF):$ == coerce(x)$Rep

    definingPolynomial() == defpol

    retract(x) == retract(x)$Rep

    retractIfCan(x) == retractIfCan(x)$Rep

    index(x) == index(x)$Rep

    lookup(x) == lookup(x)$Rep

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

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

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

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

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

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

    basis() == basis()$Rep

    0 == 0$Rep

    1 == 1$Rep

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

    representationType() == "polynomial"

    tableForDiscreteLogarithm(fac) ==
      if initlog? then initializeLog()
      tbl:=search(fac::PI,discLogTable)$Table(PI,TBL)
      tbl case "failed" =>
        error "tableForDiscreteLogarithm: argument must be prime divisor_
 of the order of the multiplicative group"
      tbl pretend TBL

    primitiveElement() ==
      if initelt? then initializeElt()
      index(primitiveElt)

    normalElement() ==
      if initelt? then initializeElt()
      index(normalElt)

    initializeElt() ==
      facOfGroupSize:=factors(factor(sizeCG)$Integer)
      -- get a primitive element
      pE:=createPrimitiveElement()
      primitiveElt:=lookup(pE)
      -- create a normal element
      nElt:=generator()
      while not normal? nElt repeat
        nElt:=nElt*pE
      normalElt:=lookup(nElt)
      -- set elements initialization flag
      initelt? := false
      void()$Void

    initializeLog() ==
      if initelt? then initializeElt()
      -- set up tables for discrete logarithm
      limit:Integer:=30
      -- the minimum size for the discrete logarithm table
      for f in facOfGroupSize repeat
        fac:=f.factor
        base:$:=primitiveElement() ** (sizeCG quo fac)
        l:Integer:=length(fac)$Integer
        n:Integer:=0
        if odd?(l)$Integer then n:=shift(fac,-(l quo 2))
                           else n:=shift(1,(l quo 2))
        if n < limit then
          d:=(fac-1) quo limit + 1
          n:=(fac-1) quo d + 1
        tbl:TBL:=table()$TBL
        a:$:=1
        for i in (0::NNI)..(n-1)::NNI repeat
          insert_!([lookup(a),i::NNI]$R,tbl)$TBL
          a:=a*base
        insert_!([fac::PI,copy(tbl)$TBL]_
               $Record(key:PI,entry:TBL),discLogTable)$Table(PI,TBL)
      -- set logarithm initialization flag
      initlog? := false
      -- tell user about initialization
      --print("discrete logarithm tables initialized"::OUT)
      void()$Void

    coerce(e:$):OutputForm == outputForm(lift(e),alpha)

    extensionDegree() == extdeg

    size() == (sizeCG + 1) pretend NNI

    inGroundField?(x) ==
      retractIfCan(x) = "failed" => false
      true

    characteristic() == characteristic()$GF