path: root/src/algebra/ffp.spad.pamphlet

\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra ffp.spad}
\author{Johannes Grabmeier, Alfred Scheerhorn, Robert Sutor, Oswald Gschnitzer}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\begin{verbatim}
-- 28.01.93: AS and JG: setting of initlog? and initelt? flags in 
--    functions initializeLog and initializeElt put at the 
--    end to avoid errors with interruption. createNormalElement() 
--    included in function initializeElt. Function createNormalElement() set
--    into comments. factorsOfCyclicGroupSize() changed.
-- 12.05.92: JG: long lines
-- 18.02.92: AS: degree: $ -> PI added, faster then category version
-- 18.06.91: AS: createNormalElement added:
--          the version in ffcat.spad needs too long
--          for finding a normal element, because of the "correlation" between
--          the "additive" structure of the index function and the additive
--          structure of the field. Our experiments show that this version is
--          much faster.
-- 05.04.91 JG: comments, IFF
-- 04.04.91 JG: error message in function tablesOfDiscreteLogarithm changed
-- 04.04.91 JG: comment of FFP was changed

\end{verbatim}

\section{domain FFP FiniteFieldExtensionByPolynomial}

<<domain FFP FiniteFieldExtensionByPolynomial>>=
)abbrev domain FFP FiniteFieldExtensionByPolynomial
++ Authors: R.Sutor, J. Grabmeier, O. Gschnitzer, A. Scheerhorn
++ Date Created:
++ Date Last Updated: May 29, 2009
++ Basic Operations:
++ Related Constructors:
++ Also See: FiniteFieldCyclicGroupExtensionByPolynomial,
++  FiniteFieldNormalBasisExtensionByPolynomial
++ AMS Classifications:
++ Keywords: field, extension field, algebraic extension,
++   finite extension, finite field, Galois field
++ Reference:
++  R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an
++   Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++   AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++   FiniteFieldExtensionByPolynomial(GF, defpol) implements the extension
++   of the finite field {\em GF} generated by the extension polynomial
++   {\em defpol} which MUST be irreducible.
++   Note: the user has the responsibility to ensure that
++   {\em defpol} is irreducible.

FiniteFieldExtensionByPolynomial(GF:FiniteFieldCategory,_
  defpol:SparseUnivariatePolynomial GF): Exports == Implementation 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

  Exports ==> FiniteAlgebraicExtensionField(GF)

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

--    createNormalElement() ==
--      a:=primitiveElement()
--      nElt:=generator()
--      for i in 1.. repeat
--        normal? nElt => return nElt
--        nElt:=nElt*a
--      nElt

    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: %): PositiveInteger ==
      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:$ / a:GF ==
--      a = 0$GF => error "division by zero"
--      x * inv(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(): PositiveInteger == extdeg

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

--  sizeOfGroundField() == size()$GF

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

    characteristic == characteristic$GF

    before?(x,y) == before?(x,y)$Rep
@
\section{domain FFX FiniteFieldExtension}
<<domain FFX FiniteFieldExtension>>=
)abbrev domain FFX FiniteFieldExtension
++ Authors: R.Sutor, J. Grabmeier, A. Scheerhorn
++ Date Created:
++ Date Last Updated: 31 March 1991
++ Basic Operations:
++ Related Constructors: FiniteFieldExtensionByPolynomial,
++  FiniteFieldPolynomialPackage
++ Also See: FiniteFieldCyclicGroupExtension,
++  FiniteFieldNormalBasisExtension
++ AMS Classifications:
++ Keywords: field, extension field, algebraic extension,
++   finite extension, finite field, Galois field
++ Reference:
++  R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an
++   Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++   AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++   FiniteFieldExtensionByPolynomial(GF, n) implements an extension
++   of the finite field {\em GF} of degree n generated by the extension
++   polynomial constructed by
++   \spadfunFrom{createIrreduciblePoly}{FiniteFieldPolynomialPackage} from
++   \spadtype{FiniteFieldPolynomialPackage}.
FiniteFieldExtension(GF, n): Exports == Implementation where
  GF: FiniteFieldCategory
  n : PositiveInteger
  Exports ==> FiniteAlgebraicExtensionField(GF)
  -- MonogenicAlgebra(GF, SUP) with  -- have to check this
  Implementation ==> FiniteFieldExtensionByPolynomial(GF,
       createIrreduciblePoly(n)$FiniteFieldPolynomialPackage(GF))
  -- old code for generating irreducible polynomials:
  -- now "better" order (sparse polys first)
  -- generateIrredPoly(n)$IrredPolyOverFiniteField(GF))

@
\section{domain IFF InnerFiniteField}
<<domain IFF InnerFiniteField>>=
)abbrev domain IFF InnerFiniteField
++ Author: ???
++ Date Created: ???
++ Date Last Updated: 29 May 1990
++ Basic Operations:
++ Related Constructors: FiniteFieldExtensionByPolynomial,
++  FiniteFieldPolynomialPackage
++ Also See: FiniteFieldCyclicGroup, FiniteFieldNormalBasis
++ AMS Classifications:
++ Keywords: field, extension field, algebraic extension,
++   finite extension, finite field, Galois field
++ Reference:
++  R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an
++   Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++   AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++   InnerFiniteField(p,n) implements finite fields with \spad{p**n} elements
++   where p is assumed prime but does not check.
++   For a version which checks that p is prime, see \spadtype{FiniteField}.
InnerFiniteField(p:PositiveInteger, n:PositiveInteger) ==
     FiniteFieldExtension(InnerPrimeField p, n)

@
\section{domain FF FiniteField}
<<domain FF FiniteField>>=
)abbrev domain FF FiniteField
++ Author: ???
++ Date Created: ???
++ Date Last Updated: 29 May 1990
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: field, extension field, algebraic extension,
++  finite extension, finite field, Galois field
++ Reference:
++  R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an
++   Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++   AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++  FiniteField(p,n) implements finite fields with p**n elements.
++  This packages checks that p is prime.
++  For a non-checking version, see \spadtype{InnerFiniteField}.
FiniteField(p:PositiveInteger, n:PositiveInteger): _
   FiniteAlgebraicExtensionField(PrimeField p) ==_
   FiniteFieldExtensionByPolynomial(PrimeField p,_
       createIrreduciblePoly(n)$FiniteFieldPolynomialPackage(PrimeField p))
  -- old code for generating irreducible polynomials:
  -- now "better" order (sparse polys first)
  -- generateIrredPoly(n)$IrredPolyOverFiniteField(GF))

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<domain FFP FiniteFieldExtensionByPolynomial>>
<<domain FFX FiniteFieldExtension>>
<<domain IFF InnerFiniteField>>
<<domain FF FiniteField>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}