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

)abbrev domain FFNBP FiniteFieldNormalBasisExtensionByPolynomial
++ Authors: J.Grabmeier, A.Scheerhorn
++ Date Created: 26.03.1991
++ Date Last Updated: 08 May 1991
++ References:
++ Grab92 Finite Fields in Axiom
++ Lidl83 Finite Field, Encyclopedia of Mathematics and Its Applications
++ Description:
++ \spad{FiniteFieldNormalBasisExtensionByPolynomial(GF,uni)} implements a
++ finite extension of the ground field GF. The elements are
++ represented by coordinate vectors with respect to a normal basis, a basis
++ consisting of the conjugates (q-powers) of an element, in this case
++ called normal element, where q is the size of GF.
++ The normal element is chosen as a root of the extension
++ polynomial, which MUST be normal over GF  (user responsibility)

FiniteFieldNormalBasisExtensionByPolynomial(GF,uni) : SIG == CODE where
  GF : FiniteFieldCategory            -- the ground field
  uni : Union(SparseUnivariatePolynomial GF,_
            Vector List Record(value:GF,index:SingleInteger))

  PI   ==> PositiveInteger
  NNI  ==> NonNegativeInteger
  I    ==> Integer
  SI   ==> SingleInteger
  SUP  ==> SparseUnivariatePolynomial
  V    ==> Vector GF
  M    ==> Matrix GF
  OUT  ==> OutputForm
  TERM ==> Record(value:GF,index:SI)
  R    ==> Record(key:PI,entry:NNI)
  TBL  ==> Table(PI,NNI)
  FFF    ==> FiniteFieldFunctions(GF)
  INBFF  ==> InnerNormalBasisFieldFunctions(GF)

  SIG ==> FiniteAlgebraicExtensionField(GF)  with

      getMultiplicationTable : () -> Vector List TERM
        ++ getMultiplicationTable() returns the multiplication
        ++ table for the normal basis of the field.
        ++ This table is used to perform multiplications between field elements.

      getMultiplicationMatrix : () -> M
        ++ getMultiplicationMatrix() returns the multiplication table in
        ++ form of a matrix.

      sizeMultiplication : () -> NNI
        ++ sizeMultiplication() returns the number of entries in the
        ++ multiplication table of the field.
        ++ Note: the time of multiplication
        ++ of field elements depends on this size.

  CODE ==> add

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

    Rep:= V     -- elements are represented by vectors over GF

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

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

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

    initmult?:Boolean:=true
    -- gets false after initialization of the multiplication
    -- table or the primitive element

    extdeg:PI   :=1

    defpol:SUP(GF):=0$SUP(GF)
    -- the defining polynomial

    multTable:Vector List TERM:=new(1,nil()$(List TERM))
    -- global variable containing the multiplication table

    if uni case (Vector List TERM) then
      multTable:=uni :: (Vector List TERM)
      extdeg:= (#multTable) pretend PI
      vv:V:=new(extdeg,0)$V
      vv.1:=1$GF
      setFieldInfo(multTable,1$GF)$INBFF
      defpol:=minimalPolynomial(vv)$INBFF
      initmult?:=false
     else
      defpol:=uni :: SUP(GF)
      extdeg:=degree(defpol)$(SUP GF) pretend PI
      multTable:Vector List TERM:=new(extdeg,nil()$(List TERM))

    basisOutput : List OUT :=
      qs:OUT:=(q::Symbol)::OUT
      append([alpha, alpha **$OUT qs],_
        [alpha **$OUT (qs **$OUT i::OUT) for i in 2..extdeg-1] )

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

    traceAlpha:GF:=-$GF coefficient(defpol,(degree(defpol)-1)::NNI)
    -- the inverse of the trace of the normalElt
    -- is computed here. It defines the imbedding of
    -- GF in the extension field

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

    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 ===========================================================

    initializeLog: ()     -> Void

    initializeElt: ()     -> Void

    initializeMult: ()     -> Void

    coerce(v:GF):$  == new(extdeg,v /$GF traceAlpha)$Rep
    represents(v)   ==  v::$

    degree(a) ==
      d:PI:=1
      b:= qPot(a::Rep,1)$INBFF
      while (b^=a) repeat
        b:= qPot(b::Rep,1)$INBFF
        d:=d+1
      d

    linearAssociatedExp(x,f) ==
      xm:SUP(GF):=monomial(1$GF,extdeg)$(SUP GF) - 1$(SUP GF)
      r:= (f * pol(x::Rep)$INBFF) rem xm
      vectorise(r,extdeg)$(SUP GF)

    linearAssociatedLog(x) ==  pol(x::Rep)$INBFF

    linearAssociatedOrder(x) ==
      xm:SUP(GF):=monomial(1$GF,extdeg)$(SUP GF) - 1$(SUP GF)
      xm quo gcd(xm,pol(x::Rep)$INBFF)

    linearAssociatedLog(b,x) ==
      zero? x => 0
      xm:SUP(GF):=monomial(1$GF,extdeg)$(SUP GF) - 1$(SUP GF)
      e:= extendedEuclidean(pol(b::Rep)$INBFF,xm,pol(x::Rep)$INBFF)$(SUP GF)
      e = "failed" => "failed"
      e1:= e :: Record(coef1:(SUP GF),coef2:(SUP GF))
      e1.coef1

    getMultiplicationTable() ==
      if initmult? then initializeMult()
      multTable

    getMultiplicationMatrix() ==
      if initmult? then initializeMult()
      createMultiplicationMatrix(multTable)$FFF

    sizeMultiplication() ==
      if initmult? then initializeMult()
      sizeMultiplication(multTable)$FFF

    trace(a:$) == retract trace(a,1)

    norm(a:$) == retract norm(a,1)

    generator() == normalElement(extdeg)$INBFF

    basis(n:PI) ==
      (extdeg rem n) ^= 0 => error "argument must divide extension degree"
      [Frobenius(trace(normalElement,n),i) for i in 0..(n-1)]::(Vector $)

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

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

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

    Frobenius(e) == qPot(e::Rep,1)$INBFF
    Frobenius(e,n) == qPot(e::Rep,n)$INBFF

    retractIfCan(x) ==
      inGroundField?(x) =>
        x.1 *$GF traceAlpha
      "failed"

    retract(x) ==
      inGroundField?(x) =>
        x.1 *$GF traceAlpha
      error("element not in ground field")

    -- to get a "normal basis like" output form
    coerce(x:$):OUT ==
      l:List OUT:=nil()$(List OUT)
      n : PI := extdeg
      (n = 1) => (x.1) :: OUT
      for i in 1..n for b in basisOutput repeat
        if not zero? x.i then
          mon : OUT :=
            (x.i = 1) => b
            ((x.i)::OUT) *$OUT b
          l:=cons(mon,l)$(List OUT)
      null(l)$(List OUT) => (0::OUT)
      r:=reduce("+",l)$(List OUT)
      r

    initializeElt() ==
      facOfGroupSize := factors factor(size()$GF**extdeg-1)$I
      -- get a primitive element
      primitiveElt:=lookup(createPrimitiveElement())
      initelt?:=false
      void()$Void

    initializeMult() ==
      multTable:=createMultiplicationTable(defpol)$FFF
      setFieldInfo(multTable,traceAlpha)$INBFF
      -- reset initialize flag
      initmult?:=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:$:=index(primitiveElt)**((size()$GF**extdeg -$I 1$I) quo$I fac)
        l:Integer:=length(fac)$Integer
        n:Integer:=0
        if odd?(l)$I then n:=shift(fac,-$I (l quo$I 2))$I
                     else n:=shift(1,l quo$I 2)$I
        if n <$I limit then
          d:=(fac -$I 1$I) quo$I limit +$I 1$I
          n:=(fac -$I 1$I) quo$I d +$I 1$I
        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)
      initlog?:=false
      -- tell user about initialization
      --print("discrete logarithm table initialized"::OUT)
      void()$Void

    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 :: TBL

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

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

    extensionDegree() == extdeg

    sizeOfGroundField() == size()$GF pretend NNI

    definingPolynomial() == defpol

    trace(a,d) ==
      v:=trace(a::Rep,d)$INBFF
      erg:=v
      for i in 2..(extdeg quo d) repeat
        erg:=concat(erg,v)$Rep
      erg

    characteristic() == characteristic()$GF

    random() == random(extdeg)$INBFF

    x:$ * y:$ ==
      if initmult? then initializeMult()
      setFieldInfo(multTable,traceAlpha)$INBFF
      x::Rep *$INBFF y::Rep

    1 == new(extdeg,inv(traceAlpha)$GF)$Rep

    0 == zero(extdeg)$Rep

    size() == size()$GF ** extdeg

    index(n:PI) == index(extdeg,n)$INBFF

    lookup(x:$) == lookup(x::Rep)$INBFF

    basis() ==
      a:=basis(extdeg)$INBFF
      vector([e::$ for e in entries a])

    x:$ ** e:I ==
      if initmult? then initializeMult()
      setFieldInfo(multTable,traceAlpha)$INBFF
      (x::Rep) **$INBFF e

    normal?(x) == normal?(x::Rep)$INBFF

    -(x:$) == -$Rep x

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

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

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

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

    representationType() == "normal"

    minimalPolynomial(a) ==
      if initmult? then initializeMult()
      setFieldInfo(multTable,traceAlpha)$INBFF
      minimalPolynomial(a::Rep)$INBFF

    -- is x an element of the ground field GF ?
    inGroundField?(x) ==
      erg:=true
      for i in 2..extdeg repeat
        not(x.i =$GF x.1) => erg:=false
      erg

    x:$ / y:$ ==
      if initmult? then initializeMult()
      setFieldInfo(multTable,traceAlpha)$INBFF
      x::Rep /$INBFF y::Rep

    inv(a) ==
      if initmult? then initializeMult()
      setFieldInfo(multTable,traceAlpha)$INBFF
      inv(a::Rep)$INBFF

    norm(a,d) ==
      if initmult? then initializeMult()
      setFieldInfo(multTable,traceAlpha)$INBFF
      norm(a::Rep,d)$INBFF

    normalElement() == normalElement(extdeg)$INBFF