Initial population.

1 files changed, 403 insertions, 0 deletions

diff --git a/src/algebra/ffp.spad.pamphlet b/src/algebra/ffp.spad.pamphlet
new file mode 100644
index 00000000..2d97d795
--- /dev/null
+++ b/src/algebra/ffp.spad.pamphlet
@@ -0,0 +1,403 @@
+\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: 31 March 1991
+++ 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) ==
+      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() == extdeg
+
+    size() == (sizeCG + 1) pretend NNI
+
+--  sizeOfGroundField() == size()$GF
+
+    inGroundField?(x) ==
+      retractIfCan(x) = "failed" => false
+      true
+
+    characteristic() == characteristic()$GF
+
+@
+\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}