Initial population.

1 files changed, 304 insertions, 0 deletions

diff --git a/src/algebra/fff.spad.pamphlet b/src/algebra/fff.spad.pamphlet
new file mode 100644
index 00000000..858b9505
--- /dev/null
+++ b/src/algebra/fff.spad.pamphlet
@@ -0,0 +1,304 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra fff.spad}
+\author{Johannes Grabmeier, Alfred Scheerhorn}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\begin{verbatim}
+-- 12.03.92: AS: generalized createLowComplexityTable
+-- 25.02.92: AS: added functions:
+--      createLowComplexityTable: PI -> Union(Vector List TERM,"failed")
+--      createLowComplexityNormalBasis: PI -> Union(SUP, V L TERM)
+
+--  Finite Field Functions
+\end{verbatim}
+\section{package FFF FiniteFieldFunctions}
+<<package FFF FiniteFieldFunctions>>=
+)abbrev package FFF FiniteFieldFunctions
+++ Author: J. Grabmeier, A. Scheerhorn
+++ Date Created: 21 March 1991
+++ Date Last Updated: 31 March 1991
+++ Basic Operations:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ References:
+++  Lidl, R. & Niederreiter, H., "Finite Fields",
+++   Encycl. of Math. 20, Addison-Wesley, 1983
+++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
+++   AXIOM Technical Report Series, ATR/5 NP2522.
+++ Description:
+++  FiniteFieldFunctions(GF) is a package with functions
+++  concerning finite extension fields of the finite ground field {\em GF},
+++  e.g. Zech logarithms.
+++ Keywords: finite field, Zech logarithm, Jacobi logarithm, normal basis
+
+FiniteFieldFunctions(GF): Exports == Implementation where
+  GF  : FiniteFieldCategory  -- the ground field
+
+  PI   ==> PositiveInteger
+  NNI  ==> NonNegativeInteger
+  I    ==> Integer
+  SI   ==> SingleInteger
+  SUP  ==> SparseUnivariatePolynomial GF
+  V    ==> Vector
+  M    ==> Matrix
+  L    ==> List
+  OUT  ==> OutputForm
+  SAE  ==> SimpleAlgebraicExtension
+  ARR  ==> PrimitiveArray(SI)
+  TERM ==> Record(value:GF,index:SI)
+  MM   ==> ModMonic(GF,SUP)
+  PF   ==> PrimeField
+
+  Exports ==> with
+
+      createZechTable: SUP -> ARR
+        ++ createZechTable(f) generates a Zech logarithm table for the cyclic
+        ++ group representation of a extension of the ground field by the
+        ++ primitive polynomial {\em f(x)}, i.e. \spad{Z(i)},
+        ++ defined by {\em x**Z(i) = 1+x**i} is stored at index i.
+        ++ This is needed in particular
+        ++ to perform addition of field elements in finite fields represented
+        ++ in this way. See \spadtype{FFCGP}, \spadtype{FFCGX}.
+      createMultiplicationTable: SUP -> V L TERM
+        ++ createMultiplicationTable(f) generates a multiplication
+        ++ table for the normal basis of the field extension determined
+        ++ by {\em f}. This is needed to perform multiplications
+        ++ between elements represented as coordinate vectors to this basis.
+        ++ See \spadtype{FFNBP}, \spadtype{FFNBX}.
+      createMultiplicationMatrix: V L TERM -> M GF
+        ++ createMultiplicationMatrix(m) forms the multiplication table
+        ++ {\em m} into a matrix over the ground field.
+        -- only useful for the user to visualise the multiplication table
+        -- in a nice form
+      sizeMultiplication: V L TERM -> NNI
+        ++ sizeMultiplication(m) returns the number of entries
+        ++ of the multiplication table {\em m}.
+        -- the time of the multiplication of field elements depends
+        -- on this size
+      createLowComplexityTable: PI -> Union(Vector List TERM,"failed")
+        ++ createLowComplexityTable(n) tries to find
+        ++ a low complexity normal basis of degree {\em n} over {\em GF}
+        ++ and returns its multiplication matrix
+        ++ Fails, if it does not find a low complexity basis
+      createLowComplexityNormalBasis: PI -> Union(SUP, V L TERM)
+        ++ createLowComplexityNormalBasis(n) tries to find a
+        ++ a low complexity normal basis of degree {\em n} over {\em GF}
+        ++ and returns its multiplication matrix
+        ++ If no low complexity basis is found it calls
+        ++ \axiomFunFrom{createNormalPoly}{FiniteFieldPolynomialPackage}(n) to produce a normal
+        ++ polynomial of degree {\em n} over {\em GF}
+
+  Implementation ==> add
+
+
+    createLowComplexityNormalBasis(n) ==
+      (u:=createLowComplexityTable(n)) case "failed" =>
+        createNormalPoly(n)$FiniteFieldPolynomialPackage(GF)
+      u::(V L TERM)
+
+-- try to find a low complexity normal basis multiplication table
+-- of the field of extension degree n
+-- the algorithm is from:
+-- Wassermann A., Konstruktion von Normalbasen,
+-- Bayreuther Mathematische Schriften 31 (1989),1-9.
+
+    createLowComplexityTable(n) ==
+      q:=size()$GF
+      -- this algorithm works only for prime fields
+      p:=characteristic()$GF
+      -- search of a suitable parameter k
+      k:NNI:=0
+      for i in 1..n-1  while (k=0) repeat
+        if prime?(i*n+1) and not(p = (i*n+1)) then
+          primitive?(q::PF(i*n+1))$PF(i*n+1) =>
+              a:NNI:=1
+              k:=i
+              t1:PF(k*n+1):=(q::PF(k*n+1))**n
+          gcd(n,a:=discreteLog(q::PF(n*i+1))$PF(n*i+1))$I = 1 =>
+              k:=i
+              t1:=primitiveElement()$PF(k*n+1)**n
+      k = 0 => "failed"
+      -- initialize some start values
+      multmat:M PF(p):=zero(n,n)
+      p1:=(k*n+1)
+      pkn:=q::PF(p1)
+      t:=t1 pretend PF(p1)
+      if odd?(k) then
+          jt:I:=(n quo 2)+1
+          vt:I:=positiveRemainder((k-a) quo 2,k)+1
+        else
+          jt:I:=1
+          vt:I:=(k quo 2)+1
+      -- compute matrix
+      vec:Vector I:=zero(p1 pretend NNI)
+      for x in 1..k repeat
+        for l in 1..n repeat
+          vec.((t**(x-1) * pkn**(l-1)) pretend Integer+1):=_
+                                            positiveRemainder(l,p1)
+      lvj:M I:=zero(k::NNI,n)
+      for v in 1..k repeat
+        for j in 1..n repeat
+          if (j^=jt) or (v^=vt) then
+            help:PF(p1):=t**(v-1)*pkn**(j-1)+1@PF(p1)
+            setelt(lvj,v,j,vec.(help pretend I +1))
+      for j in 1..n repeat
+        if j^=jt then
+          for v in 1..k repeat
+            lvjh:=elt(lvj,v,j)
+            setelt(multmat,j,lvjh,elt(multmat,j,lvjh)+1)
+      for i in 1..n repeat
+        setelt(multmat,jt,i,positiveRemainder(-k,p)::PF(p))
+      for v in 1..k repeat
+        if v^=vt then
+          lvjh:=elt(lvj,v,jt)
+          setelt(multmat,jt,lvjh,elt(multmat,jt,lvjh)+1)
+      -- multmat
+      m:=nrows(multmat)$(M PF(p))
+      multtable:V L TERM:=new(m,nil()$(L TERM))$(V L TERM)
+      for i in 1..m repeat
+        l:L TERM:=nil()$(L TERM)
+        v:V PF(p):=row(multmat,i)
+        for j in (1::I)..(m::I) repeat
+          if (v.j ^= 0) then
+            -- take -v.j to get trace 1 instead of -1
+            term:TERM:=[(convert(-v.j)@I)::GF,(j-2) pretend SI]$TERM
+            l:=cons(term,l)$(L TERM)
+        qsetelt_!(multtable,i,copy l)$(V L TERM)
+      multtable
+
+    sizeMultiplication(m) ==
+      s:NNI:=0
+      for i in 1..#m repeat
+        s := s + #(m.i)
+      s
+
+    createMultiplicationTable(f:SUP) ==
+      sizeGF:NNI:=size()$GF -- the size of the ground field
+      m:PI:=degree(f)$SUP pretend PI
+      m=1 =>
+        [[[-coefficient(f,0)$SUP,(-1)::SI]$TERM]$(L TERM)]::(V L TERM)
+      m1:I:=m-1
+      -- initialize basis change matrices
+      setPoly(f)$MM
+      e:=reduce(monomial(1,1)$SUP)$MM ** sizeGF
+      w:=1$MM
+      qpow:PrimitiveArray(MM):=new(m,0)
+      qpow.0:=1$MM
+      for i in 1..m1 repeat
+        qpow.i:=(w:=w*e)
+      -- qpow.i = x**(i*q)
+      qexp:PrimitiveArray(MM):=new(m,0)
+      qexp.0:=reduce(monomial(1,1)$SUP)$MM
+      mat:M GF:=zero(m,m)$(M GF)
+      qsetelt_!(mat,2,1,1$GF)$(M GF)
+      h:=qpow.1
+      qexp.1:=h
+      setColumn_!(mat,2,Vectorise(h)$MM)$(M GF)
+      for i in 2..m1 repeat
+        g:=0$MM
+        while h ^= 0 repeat
+          g:=g + leadingCoefficient(h) * qpow.degree(h)$MM
+          h:=reductum(h)$MM
+        qexp.i:=g
+        setColumn_!(mat,i+1,Vectorise(h:=g)$MM)$(M GF)
+      -- loop invariant: qexp.i = x**(q**i)
+      mat1:=inverse(mat)$(M GF)
+      mat1 = "failed" =>
+        error "createMultiplicationTable: polynomial must be normal"
+      mat:=mat1 :: (M GF)
+      -- initialize multiplication table
+      multtable:V L TERM:=new(m,nil()$(L TERM))$(V L TERM)
+      for i in 1..m repeat
+        l:L TERM:=nil()$(L TERM)
+        v:V GF:=mat *$(M GF) Vectorise(qexp.(i-1) *$MM qexp.0)$MM
+        for j in (1::SI)..(m::SI) repeat
+          if (v.j ^= 0$GF) then
+            term:TERM:=[(v.j),j-(2::SI)]$TERM
+            l:=cons(term,l)$(L TERM)
+        qsetelt_!(multtable,i,copy l)$(V L TERM)
+      multtable
+
+
+    createZechTable(f:SUP) ==
+      sizeGF:NNI:=size()$GF -- the size of the ground field
+      m:=degree(f)$SUP::PI
+      qm1:SI:=(sizeGF ** m -1) pretend SI
+      zechlog:ARR:=new(((sizeGF ** m + 1) quo 2)::NNI,-1::SI)$ARR
+      helparr:ARR:=new(sizeGF ** m::NNI,0$SI)$ARR
+      primElement:=reduce(monomial(1,1)$SUP)$SAE(GF,SUP,f)
+      a:=primElement
+      for i in 1..qm1-1 repeat
+        helparr.(lookup(a -$SAE(GF,SUP,f) 1$SAE(GF,SUP,f)_
+           )$SAE(GF,SUP,f)):=i::SI
+        a:=a * primElement
+      characteristic() = 2 =>
+        a:=primElement
+        for i in 1..(qm1 quo 2) repeat
+          zechlog.i:=helparr.lookup(a)$SAE(GF,SUP,f)
+          a:=a * primElement
+        zechlog
+      a:=1$SAE(GF,SUP,f)
+      for i in 0..((qm1-2) quo 2) repeat
+        zechlog.i:=helparr.lookup(a)$SAE(GF,SUP,f)
+        a:=a * primElement
+      zechlog
+
+    createMultiplicationMatrix(m) ==
+      n:NNI:=#m
+      mat:M GF:=zero(n,n)$(M GF)
+      for i in 1..n repeat
+        for t in m.i repeat
+          qsetelt_!(mat,i,t.index+2,t.value)
+      mat
+
+@
+\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>>
+
+<<package FFF FiniteFieldFunctions>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}