Initial population.

1 files changed, 873 insertions, 0 deletions

diff --git a/src/algebra/ffcat.spad.pamphlet b/src/algebra/ffcat.spad.pamphlet
new file mode 100644
index 00000000..9505c555
--- /dev/null
+++ b/src/algebra/ffcat.spad.pamphlet
@@ -0,0 +1,873 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra ffcat.spad}
+\author{Johannes Grabmeier, Alfred Scheerhorn, Barry Trager, James Davenport}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\begin{verbatim}
+-- 28.01.93: AS and JG:another Error in discreteLog(.,.) in FFIEDLC corrected.
+-- 08.05.92: AS  Error in discreteLog(.,.) in FFIEDLC corrected.
+-- 03.04.92: AS  Barry Trager added package FFSLPE and some functions to FFIELDC
+-- 25.02.92: AS  added following functions in FAXF: impl.of mrepresents,
+--               linearAssociatedExp,linearAssociatedLog, linearAssociatedOrder
+-- 18.02.92: AS: more efficient version of degree added,
+--               first version of degree in FAXF set into comments
+-- 18.06.91: AS: general version of minimalPolynomial added
+-- 08.05.91: JG, AS implementation of missing functions in FFC and FAXF
+-- 04.05.91: JG: comments
+-- 04.04.91: JG: old version of charthRoot in FFC was dropped
+
+-- Fields with finite characteristic
+\end{verbatim}
+\section{category FPC FieldOfPrimeCharacteristic}
+<<category FPC FieldOfPrimeCharacteristic>>=
+)abbrev category FPC FieldOfPrimeCharacteristic
+++ Author: J. Grabmeier, A. Scheerhorn
+++ Date Created: 10 March 1991
+++ Date Last Updated: 31 March 1991
+++ Basic Operations: _+, _*
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords: field, finite field, prime characteristic
+++ References:
+++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
+++  AXIOM Technical Report Series, ATR/5 NP2522.
+++ Description:
+++  FieldOfPrimeCharacteristic is the category of fields of prime
+++  characteristic, e.g. finite fields, algebraic closures of
+++  fields of prime characteristic, transcendental extensions of
+++  of fields of prime characteristic.
+FieldOfPrimeCharacteristic:Category == _
+  Join(Field,CharacteristicNonZero) with
+    order: $ -> OnePointCompletion PositiveInteger
+      ++ order(a) computes the order of an element in the multiplicative
+      ++ group of the field.
+      ++ Error: if \spad{a} is 0.
+    discreteLog: ($,$) -> Union(NonNegativeInteger,"failed")
+      ++ discreteLog(b,a) computes s with \spad{b**s = a} if such an s exists.
+    primeFrobenius: $ -> $
+      ++ primeFrobenius(a) returns \spad{a ** p} where p is the characteristic.
+    primeFrobenius: ($,NonNegativeInteger) -> $
+      ++ primeFrobenius(a,s) returns \spad{a**(p**s)} where p
+      ++ is the characteristic.
+  add
+    primeFrobenius(a) == a ** characteristic()
+    primeFrobenius(a,s) == a ** (characteristic()**s)
+
+@
+\section{category XF ExtensionField}
+<<category XF ExtensionField>>=
+)abbrev category XF ExtensionField
+++ Author: J. Grabmeier, A. Scheerhorn
+++ Date Created: 10 March 1991
+++ Date Last Updated: 31 March 1991
+++ Basic Operations: _+, _*, extensionDegree, algebraic?, transcendent?
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords: field, extension field
+++ References:
+++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
+++  AXIOM Technical Report Series, ATR/5 NP2522.
+++ Description:
+++  ExtensionField {\em F} is the category of fields which extend
+++  the field F
+ExtensionField(F:Field) : Category  == Join(Field,RetractableTo F,VectorSpace F) with
+    if F has CharacteristicZero then CharacteristicZero
+    if F has CharacteristicNonZero then FieldOfPrimeCharacteristic
+    algebraic? : $ -> Boolean
+      ++ algebraic?(a) tests whether an element \spad{a} is algebraic with
+      ++ respect to the ground field F.
+    transcendent? : $ -> Boolean
+      ++ transcendent?(a) tests whether an element \spad{a} is transcendent
+      ++ with respect to the ground field F.
+    inGroundField?: $ -> Boolean
+      ++ inGroundField?(a) tests whether an element \spad{a}
+      ++ is already in the ground field F.
+    degree : $ -> OnePointCompletion PositiveInteger
+      ++ degree(a) returns the degree of minimal polynomial of an element
+      ++ \spad{a} if \spad{a} is algebraic
+      ++ with respect to the ground field F, and \spad{infinity} otherwise.
+    extensionDegree : () -> OnePointCompletion PositiveInteger
+      ++ extensionDegree() returns the degree of the field extension if the
+      ++ extension is algebraic, and \spad{infinity} if it is not.
+    transcendenceDegree : () -> NonNegativeInteger
+      ++ transcendenceDegree() returns the transcendence degree of the
+      ++ field extension, 0 if the extension is algebraic.
+    -- perhaps more absolute degree functions
+    if F has Finite then
+      FieldOfPrimeCharacteristic
+      Frobenius: $ -> $
+        ++ Frobenius(a) returns \spad{a ** q} where q is the \spad{size()$F}.
+      Frobenius:   ($,NonNegativeInteger) -> $
+        ++ Frobenius(a,s) returns \spad{a**(q**s)} where q is the size()$F.
+  add
+    algebraic?(a) == not infinite? (degree(a)@OnePointCompletion_
+      (PositiveInteger))$OnePointCompletion(PositiveInteger)
+    transcendent? a == infinite?(degree(a)@OnePointCompletion _
+      (PositiveInteger))$OnePointCompletion(PositiveInteger)
+    if F has Finite then
+      Frobenius(a) == a ** size()$F
+      Frobenius(a,s) == a ** (size()$F ** s)
+
+@
+\section{category FAXF FiniteAlgebraicExtensionField}
+<<category FAXF FiniteAlgebraicExtensionField>>=
+)abbrev category FAXF FiniteAlgebraicExtensionField
+++ Author: J. Grabmeier, A. Scheerhorn
+++ Date Created: 11 March 1991
+++ Date Last Updated: 31 March 1991
+++ Basic Operations: _+, _*, extensionDegree,
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords: field, extension field, algebraic extension, finite extension
+++ References:
+++  R.Lidl, H.Niederreiter: Finite Field, Encycoldia of Mathematics and
+++  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:
+++  FiniteAlgebraicExtensionField {\em F} is the category of fields
+++  which are finite algebraic extensions of the field {\em F}.
+++  If {\em F} is finite then any finite algebraic extension of {\em F} is finite, too.
+++  Let {\em K} be a finite algebraic extension of the finite field {\em F}.
+++  The exponentiation of elements of {\em K} defines a Z-module structure
+++  on the multiplicative group of {\em K}. The additive group of {\em K}
+++  becomes a module over the ring of polynomials over {\em F} via the operation
+++  \spadfun{linearAssociatedExp}(a:K,f:SparseUnivariatePolynomial F)
+++  which is linear over {\em F}, i.e. for elements {\em a} from {\em K},
+++  {\em c,d} from {\em F} and {\em f,g} univariate polynomials over {\em F}
+++  we have \spadfun{linearAssociatedExp}(a,cf+dg) equals {\em c} times
+++  \spadfun{linearAssociatedExp}(a,f) plus {\em d} times
+++  \spadfun{linearAssociatedExp}(a,g).
+++  Therefore \spadfun{linearAssociatedExp} is defined completely by
+++  its action on  monomials from {\em F[X]}:
+++  \spadfun{linearAssociatedExp}(a,monomial(1,k)\$SUP(F)) is defined to be
+++  \spadfun{Frobenius}(a,k) which is {\em a**(q**k)} where {\em q=size()\$F}.
+++  The operations order and discreteLog associated with the multiplicative
+++  exponentiation have additive analogues associated to the operation
+++  \spadfun{linearAssociatedExp}. These are the functions
+++  \spadfun{linearAssociatedOrder} and \spadfun{linearAssociatedLog},
+++  respectively.
+
+FiniteAlgebraicExtensionField(F : Field) : Category == _
+  Join(ExtensionField F, RetractableTo F) with
+  -- should be unified with algebras
+  -- Join(ExtensionField F, FramedAlgebra F, RetractableTo F) with
+    basis : () -> Vector $
+      ++ basis() returns a fixed basis of \$ as \spad{F}-vectorspace.
+    basis : PositiveInteger -> Vector $
+      ++ basis(n) returns a fixed basis of a subfield of \$ as
+      ++ \spad{F}-vectorspace.
+    coordinates : $ -> Vector F
+      ++ coordinates(a) returns the coordinates of \spad{a} with respect
+      ++ to the fixed \spad{F}-vectorspace basis.
+    coordinates : Vector $ -> Matrix F
+      ++ coordinates([v1,...,vm]) returns the coordinates of the
+      ++ vi's with to the fixed basis.  The coordinates of vi are
+      ++ contained in the ith row of the matrix returned by this
+      ++ function.
+    represents:  Vector F -> $
+      ++ represents([a1,..,an]) returns \spad{a1*v1 + ... + an*vn}, where
+      ++ v1,...,vn are the elements of the fixed basis.
+    minimalPolynomial: $ -> SparseUnivariatePolynomial F
+      ++ minimalPolynomial(a) returns the minimal polynomial of an
+      ++ element \spad{a} over the ground field F.
+    definingPolynomial: () -> SparseUnivariatePolynomial F
+      ++ definingPolynomial() returns the polynomial used to define
+      ++ the field extension.
+    extensionDegree : () ->  PositiveInteger
+      ++ extensionDegree() returns the degree of field extension.
+    degree : $ -> PositiveInteger
+      ++ degree(a) returns the degree of the minimal polynomial of an
+      ++ element \spad{a} over the ground field F.
+    norm: $  -> F
+      ++ norm(a) computes the norm of \spad{a} with respect to the
+      ++ field considered as an algebra with 1 over the ground field F.
+    trace: $ -> F
+      ++ trace(a) computes the trace of \spad{a} with respect to
+      ++ the field considered as an algebra with 1 over the ground field F.
+    if F has Finite then
+      FiniteFieldCategory
+      minimalPolynomial: ($,PositiveInteger) -> SparseUnivariatePolynomial $
+        ++ minimalPolynomial(x,n) computes the minimal polynomial of x over
+        ++ the field of extension degree n over the ground field F.
+      norm: ($,PositiveInteger)  -> $
+        ++ norm(a,d) computes the norm of \spad{a} with respect to the field of
+        ++ extension degree d over the ground field of size.
+        ++ Error: if d does not divide the extension degree of \spad{a}.
+        ++ Note: norm(a,d) = reduce(*,[a**(q**(d*i)) for i in 0..n/d])
+      trace: ($,PositiveInteger)   -> $
+        ++ trace(a,d) computes the trace of \spad{a} with respect to the
+        ++ field of extension degree d over the ground field of size q.
+        ++ Error: if d does not divide the extension degree of \spad{a}.
+        ++ Note: \spad{trace(a,d) = reduce(+,[a**(q**(d*i)) for i in 0..n/d])}.
+      createNormalElement: () -> $
+        ++ createNormalElement() computes a normal element over the ground
+        ++ field F, that is,
+        ++ \spad{a**(q**i), 0 <= i < extensionDegree()} is an F-basis,
+        ++ where \spad{q = size()\$F}.
+        ++ Reference: Such an element exists Lidl/Niederreiter: Theorem 2.35.
+      normalElement: () -> $
+        ++ normalElement() returns a element, normal over the ground field F,
+        ++ i.e. \spad{a**(q**i), 0 <= i < extensionDegree()} is an F-basis,
+        ++ where \spad{q = size()\$F}.
+        ++ At the first call, the element is computed by
+        ++ \spadfunFrom{createNormalElement}{FiniteAlgebraicExtensionField}
+        ++ then cached in a global variable.
+        ++ On subsequent calls, the element is retrieved by referencing the
+        ++ global variable.
+      normal?: $ -> Boolean
+        ++ normal?(a) tests whether the element \spad{a} is normal over the
+        ++ ground field F, i.e.
+        ++ \spad{a**(q**i), 0 <= i <= extensionDegree()-1} is an F-basis,
+        ++ where \spad{q = size()\$F}.
+        ++ Implementation according to Lidl/Niederreiter: Theorem 2.39.
+      generator: () -> $
+        ++ generator() returns a root of the defining polynomial.
+        ++ This element generates the field as an algebra over the ground field.
+      linearAssociatedExp:($,SparseUnivariatePolynomial F) -> $
+        ++ linearAssociatedExp(a,f) is linear over {\em F}, i.e.
+        ++ for elements {\em a} from {\em \$}, {\em c,d} form {\em F} and
+        ++ {\em f,g} univariate polynomials over {\em F} we have
+        ++ \spadfun{linearAssociatedExp}(a,cf+dg) equals {\em c} times
+        ++ \spadfun{linearAssociatedExp}(a,f) plus {\em d} times
+        ++ \spadfun{linearAssociatedExp}(a,g). Therefore
+        ++ \spadfun{linearAssociatedExp} is defined completely by its action on
+        ++ monomials from {\em F[X]}:
+        ++ \spadfun{linearAssociatedExp}(a,monomial(1,k)\$SUP(F)) is defined to
+        ++ be \spadfun{Frobenius}(a,k) which is {\em a**(q**k)},
+        ++ where {\em q=size()\$F}.
+      linearAssociatedOrder: $ -> SparseUnivariatePolynomial F
+        ++ linearAssociatedOrder(a) retruns the monic polynomial {\em g} of
+        ++ least degree, such that \spadfun{linearAssociatedExp}(a,g) is 0.
+      linearAssociatedLog: $ -> SparseUnivariatePolynomial F
+        ++ linearAssociatedLog(a) returns a polynomial {\em g}, such that
+        ++ \spadfun{linearAssociatedExp}(normalElement(),g) equals {\em a}.
+      linearAssociatedLog: ($,$) -> Union(SparseUnivariatePolynomial F,"failed")
+        ++ linearAssociatedLog(b,a) returns a polynomial {\em g}, such that the
+        ++ \spadfun{linearAssociatedExp}(b,g) equals {\em a}.
+        ++ If there is no such polynomial {\em g}, then
+        ++ \spadfun{linearAssociatedLog} fails.
+  add
+    I   ==> Integer
+    PI  ==> PositiveInteger
+    NNI ==> NonNegativeInteger
+    SUP ==> SparseUnivariatePolynomial
+    DLP ==> DiscreteLogarithmPackage
+
+    represents(v) ==
+      a:$:=0
+      b:=basis()
+      for i in 1..extensionDegree()@PI repeat
+        a:=a+(v.i)*(b.i)
+      a
+    transcendenceDegree() == 0$NNI
+    dimension() == (#basis()) ::NonNegativeInteger::CardinalNumber
+    extensionDegree():OnePointCompletion(PositiveInteger) ==
+      (#basis()) :: PositiveInteger::OnePointCompletion(PositiveInteger)
+    degree(a):OnePointCompletion(PositiveInteger) ==
+      degree(a)@PI::OnePointCompletion(PositiveInteger)
+
+    coordinates(v:Vector $) ==
+      m := new(#v, extensionDegree(), 0)$Matrix(F)
+      for i in minIndex v .. maxIndex v for j in minRowIndex m .. repeat
+        setRow_!(m, j, coordinates qelt(v, i))
+      m
+    algebraic? a == true
+    transcendent? a == false
+    extensionDegree() == (#basis()) :: PositiveInteger
+    -- degree a == degree(minimalPolynomial a)$SUP(F) :: PI
+    trace a ==
+      b := basis()
+      abs : F := 0
+      for i in 1..#b repeat
+        abs := abs + coordinates(a*b.i).i
+      abs
+    norm a ==
+      b := basis()
+      m := new(#b,#b, 0)$Matrix(F)
+      for i in 1..#b repeat
+        setRow_!(m,i, coordinates(a*b.i))
+      determinant(m)
+    if F has Finite then
+      linearAssociatedExp(x,f) ==
+        erg:$:=0
+        y:=x
+        for i in 0..degree(f) repeat
+          erg:=erg + coefficient(f,i) * y
+          y:=Frobenius(y)
+        erg
+      linearAssociatedLog(b,x) ==
+        x=0 => 0
+        l:List List F:=[entries coordinates b]
+        a:$:=b
+        extdeg:NNI:=extensionDegree()@PI
+        for i in 2..extdeg repeat
+          a:=Frobenius(a)
+          l:=concat(l,entries coordinates a)$(List List F)
+        l:=concat(l,entries coordinates x)$(List List F)
+        m1:=rowEchelon transpose matrix(l)$(Matrix F)
+        v:=zero(extdeg)$(Vector F)
+        rown:I:=1
+        for i in 1..extdeg repeat
+          if qelt(m1,rown,i) = 1$F then
+            v.i:=qelt(m1,rown,extdeg+1)
+            rown:=rown+1
+        p:=+/[monomial(v.(i+1),i::NNI) for i in 0..(#v-1)]
+        p=0 =>
+         messagePrint("linearAssociatedLog: second argument not in_
+                       group generated by first argument")$OutputForm
+         "failed"
+        p
+      linearAssociatedLog(x) == linearAssociatedLog(normalElement(),x) ::
+                              SparseUnivariatePolynomial(F)
+      linearAssociatedOrder(x) ==
+        x=0 => 0
+        l:List List F:=[entries coordinates x]
+        a:$:=x
+        for i in 1..extensionDegree()@PI repeat
+          a:=Frobenius(a)
+          l:=concat(l,entries coordinates a)$(List List F)
+        v:=first nullSpace transpose matrix(l)$(Matrix F)
+        +/[monomial(v.(i+1),i::NNI) for i in 0..(#v-1)]
+
+      charthRoot(x):Union($,"failed") ==
+        (charthRoot(x)@$)::Union($,"failed")
+      -- norm(e) == norm(e,1) pretend F
+      -- trace(e) == trace(e,1) pretend F
+      minimalPolynomial(a,n) ==
+        extensionDegree()@PI rem n ^= 0 =>
+          error "minimalPolynomial: 2. argument must divide extension degree"
+        f:SUP $:=monomial(1,1)$(SUP $) - monomial(a,0)$(SUP $)
+        u:$:=Frobenius(a,n)
+        while not(u = a) repeat
+          f:=f * (monomial(1,1)$(SUP $) - monomial(u,0)$(SUP $))
+          u:=Frobenius(u,n)
+        f
+      norm(e,s) ==
+        qr := divide(extensionDegree(), s)
+        zero?(qr.remainder) =>
+          pow := (size()-1) quo (size()$F ** s - 1)
+          e ** (pow::NonNegativeInteger)
+        error "norm: second argument must divide degree of extension"
+      trace(e,s) ==
+        qr:=divide(extensionDegree(),s)
+        q:=size()$F
+        zero?(qr.remainder) =>
+          a:$:=0
+          for i in 0..qr.quotient-1 repeat
+            a:=a + e**(q**(s*i))
+          a
+        error "trace: second argument must divide degree of extension"
+      size() == size()$F ** extensionDegree()
+      createNormalElement() ==
+        characteristic() = size() => 1
+        res : $
+        for i in 1.. repeat
+          res := index(i :: PI)
+          not inGroundField? res =>
+            normal? res => return res
+        -- theorem: there exists a normal element, this theorem is
+        -- unknown to the compiler
+        res
+      normal?(x:$) ==
+        p:SUP $:=(monomial(1,extensionDegree()) - monomial(1,0))@(SUP $)
+        f:SUP $:= +/[monomial(Frobenius(x,i),i)$(SUP $) _
+                   for i in 0..extensionDegree()-1]
+        gcd(p,f) = 1 => true
+        false
+      degree a ==
+        y:$:=Frobenius a
+        deg:PI:=1
+        while y^=a repeat
+          y := Frobenius(y)
+          deg:=deg+1
+        deg
+
+@
+\section{package DLP DiscreteLogarithmPackage}
+<<package DLP DiscreteLogarithmPackage>>=
+)abbrev package DLP DiscreteLogarithmPackage
+++ Author: J. Grabmeier, A. Scheerhorn
+++ Date Created: 12 March 1991
+++ Date Last Updated: 31 March 1991
+++ Basic Operations:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords: discrete logarithm
+++ References:
+++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
+++  AXIOM Technical Report Series, ATR/5 NP2522.
+++ Description:
+++  DiscreteLogarithmPackage implements help functions for discrete logarithms
+++  in monoids using small cyclic groups.
+
+DiscreteLogarithmPackage(M): public == private where
+  M : Join(Monoid,Finite) with
+   "**": (M,Integer) -> M
+	++ x ** n returns x raised to the integer power n
+  public ==> with
+    shanksDiscLogAlgorithm:(M,M,NonNegativeInteger)->  _
+        Union(NonNegativeInteger,"failed")
+      ++ shanksDiscLogAlgorithm(b,a,p) computes s with \spad{b**s = a} for
+      ++ assuming that \spad{a} and b are elements in a 'small' cyclic group of
+      ++ order p by Shank's algorithm.
+      ++ Note: this is a subroutine of the function \spadfun{discreteLog}.
+  I   ==> Integer
+  PI  ==> PositiveInteger
+  NNI ==> NonNegativeInteger
+  SUP ==> SparseUnivariatePolynomial
+  DLP ==> DiscreteLogarithmPackage
+
+  private ==> add
+    shanksDiscLogAlgorithm(logbase,c,p) ==
+      limit:Integer:= 30
+      -- for logarithms up to cyclic groups of order limit a full
+      -- logarithm table is computed
+      p < limit =>
+        a:M:=1
+        disclog:Integer:=0
+        found:Boolean:=false
+        for i in 0..p-1 while not found repeat
+          a = c =>
+            disclog:=i
+            found:=true
+          a:=a*logbase
+        not found =>
+          messagePrint("discreteLog: second argument not in cyclic group_
+ generated by first argument")$OutputForm
+          "failed"
+        disclog pretend NonNegativeInteger
+      l:Integer:=length(p)$Integer
+      if odd?(l)$Integer then n:Integer:= shift(p,-(l quo 2))
+                         else n:Integer:= shift(1,(l quo 2))
+      a:M:=1
+      exptable : Table(PI,NNI) :=table()$Table(PI,NNI)
+      for i in (0::NNI)..(n-1)::NNI repeat
+        insert_!([lookup(a),i::NNI]$Record(key:PI,entry:NNI),_
+                  exptable)$Table(PI,NNI)
+        a:=a*logbase
+      found := false
+      end := (p-1) quo n
+      disclog:Integer:=0
+      a := c
+      b := logbase ** (-n)
+      for i in 0..end while not found repeat
+        rho:= search(lookup(a),exptable)_
+              $Table(PositiveInteger,NNI)
+        rho case NNI =>
+          found := true
+          disclog:= n * i + rho pretend Integer
+        a := a * b
+      not found =>
+        messagePrint("discreteLog: second argument not in cyclic group_
+ generated by first argument")$OutputForm
+        "failed"
+      disclog pretend NonNegativeInteger
+
+@
+\section{category FFIELDC FiniteFieldCategory}
+<<category FFIELDC FiniteFieldCategory>>=
+)abbrev category FFIELDC FiniteFieldCategory
+++ Author: J. Grabmeier, A. Scheerhorn
+++ Date Created: 11 March 1991
+++ Date Last Updated: 31 March 1991
+++ Basic Operations: _+, _*, extensionDegree, order, primitiveElement
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords: field, extension field, algebraic extension, finite field
+++  Galois field
+++ References:
+++  D.Lipson, Elements of Algebra and Algebraic Computing, The
+++  Benjamin/Cummings Publishing Company, Inc.-Menlo Park, California, 1981.
+++  J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
+++  AXIOM Technical Report Series, ATR/5 NP2522.
+++ Description:
+++  FiniteFieldCategory is the category of finite fields
+
+FiniteFieldCategory() : Category ==_
+  Join(FieldOfPrimeCharacteristic,Finite,StepThrough,DifferentialRing) with
+--                 ,PolynomialFactorizationExplicit) with
+    charthRoot: $ -> $
+      ++ charthRoot(a) takes the characteristic'th root of {\em a}.
+      ++ Note: such a root is alway defined in finite fields.
+    conditionP: Matrix $ -> Union(Vector $,"failed")
+      ++ conditionP(mat), given a matrix representing a homogeneous system
+      ++ of equations, returns a vector whose characteristic'th powers
+      ++ is a non-trivial solution, or "failed" if no such vector exists.
+    -- the reason for implementing the following function is that we
+    -- can implement the functions order, getGenerator and primitive? on
+    -- category level without computing the, may be time intensive,
+    -- factorization of size()-1 at every function call again.
+    factorsOfCyclicGroupSize:_
+      () -> List Record(factor:Integer,exponent:Integer)
+      ++ factorsOfCyclicGroupSize() returns the factorization of size()-1
+    -- the reason for implementing the function tableForDiscreteLogarithm
+    -- is that we can implement the functions discreteLog and
+    -- shanksDiscLogAlgorithm on category level
+    -- computing the necessary exponentiation tables in the respective
+    -- domains once and for all
+    -- absoluteDegree : $ -> PositiveInteger
+    --  ++ degree of minimal polynomial, if algebraic with respect
+    --  ++ to the prime subfield
+    tableForDiscreteLogarithm: Integer -> _
+             Table(PositiveInteger,NonNegativeInteger)
+      ++ tableForDiscreteLogarithm(a,n) returns a table of the discrete
+      ++ logarithms of \spad{a**0} up to \spad{a**(n-1)} which, called with
+      ++ key \spad{lookup(a**i)} returns i for i in \spad{0..n-1}.
+      ++ Error: if not called for prime divisors of order of
+      ++        multiplicative group.
+    createPrimitiveElement: () -> $
+      ++ createPrimitiveElement() computes a generator of the (cyclic)
+      ++ multiplicative group of the field.
+      -- RDJ: Are these next lines to be included?
+      -- we run through the field and test, algorithms which construct
+      -- elements of larger order were found to be too slow
+    primitiveElement: () -> $
+      ++ primitiveElement() returns a primitive element stored in a global
+      ++ variable in the domain.
+      ++ At first call, the primitive element is computed
+      ++ by calling \spadfun{createPrimitiveElement}.
+    primitive?: $ -> Boolean
+      ++ primitive?(b) tests whether the element b is a generator of the
+      ++ (cyclic) multiplicative group of the field, i.e. is a primitive
+      ++ element.
+      ++ Implementation Note: see ch.IX.1.3, th.2 in D. Lipson.
+    discreteLog: $ -> NonNegativeInteger
+      ++ discreteLog(a) computes the discrete logarithm of \spad{a}
+      ++ with respect to \spad{primitiveElement()} of the field.
+    order: $ -> PositiveInteger
+      ++ order(b) computes the order of an element b in the multiplicative
+      ++ group of the field.
+      ++ Error: if b equals 0.
+    representationType: () -> Union("prime","polynomial","normal","cyclic")
+      ++ representationType() returns the type of the representation, one of:
+      ++ \spad{prime}, \spad{polynomial}, \spad{normal}, or \spad{cyclic}.
+  add
+    I   ==> Integer
+    PI  ==> PositiveInteger
+    NNI ==> NonNegativeInteger
+    SUP ==> SparseUnivariatePolynomial
+    DLP ==> DiscreteLogarithmPackage
+
+    -- exported functions
+
+    differentiate x          == 0
+    init() == 0
+    nextItem(a) ==
+      zero?(a:=index(lookup(a)+1)) => "failed"
+      a
+    order(e):OnePointCompletion(PositiveInteger) ==
+      (order(e)@PI)::OnePointCompletion(PositiveInteger)
+
+    conditionP(mat:Matrix $) ==
+      l:=nullSpace mat
+      empty? l or every?(zero?, first l) => "failed"
+      map(charthRoot,first l)
+    charthRoot(x:$):$ == x**(size() quo characteristic())
+    charthRoot(x:%):Union($,"failed") ==
+        (charthRoot(x)@$)::Union($,"failed")
+    createPrimitiveElement() ==
+      sm1  : PositiveInteger := (size()$$-1) pretend PositiveInteger
+      start : Integer :=
+        -- in the polynomial case, index from 1 to characteristic-1
+        -- gives prime field elements
+        representationType = "polynomial" => characteristic()::Integer
+        1
+      found : Boolean := false
+      for i in start..  while not found repeat
+        e : $ := index(i::PositiveInteger)
+        found := (order(e) = sm1)
+      e
+    primitive? a ==
+      -- add special implementation for prime field case
+      zero?(a) => false
+      explist := factorsOfCyclicGroupSize()
+      q:=(size()-1)@Integer
+      equalone : Boolean := false
+      for exp in explist while not equalone repeat
+--        equalone := one?(a**(q quo exp.factor))
+        equalone := ((a**(q quo exp.factor)) = 1)
+      not equalone
+    order e ==
+      e = 0 => error "order(0) is not defined "
+      ord:Integer:= size()-1 -- order e divides ord
+      a:Integer:= 0
+      lof:=factorsOfCyclicGroupSize()
+      for rec in lof repeat -- run through prime divisors
+        a := ord quo (primeDivisor := rec.factor)
+--        goon := one?(e**a)
+        goon := ((e**a) = 1)
+        -- run through exponents of the prime divisors
+        for j in 0..(rec.exponent)-2 while goon repeat
+          -- as long as we get (e**ord = 1) we
+          -- continue dividing by primeDivisor
+          ord := a
+          a := ord quo primeDivisor
+--          goon := one?(e**a)
+          goon := ((e**a) = 1)
+        if goon then ord := a
+        -- as we do a top down search we have found the
+        -- correct exponent of primeDivisor in order e
+        -- and continue with next prime divisor
+      ord pretend PositiveInteger
+    discreteLog(b) ==
+      zero?(b) => error "discreteLog: logarithm of zero"
+      faclist:=factorsOfCyclicGroupSize()
+      a:=b
+      gen:=primitiveElement()
+      -- in GF(2) its necessary to have discreteLog(1) = 1
+      b = gen => 1
+      disclog:Integer:=0
+      mult:Integer:=1
+      groupord := (size() - 1)@Integer
+      exp:Integer:=groupord
+      for f in faclist repeat
+        fac:=f.factor
+        for t in 0..f.exponent-1 repeat
+          exp:=exp quo fac
+          -- shanks discrete logarithm algorithm
+          exptable:=tableForDiscreteLogarithm(fac)
+          n:=#exptable
+          c:=a**exp
+          end:=(fac - 1) quo n
+          found:=false
+          disc1:Integer:=0
+          for i in 0..end while not found repeat
+            rho:= search(lookup(c),exptable)_
+                  $Table(PositiveInteger,NNI)
+            rho case NNI =>
+              found := true
+              disc1:=((n * i + rho)@Integer) * mult
+            c:=c* gen**((groupord quo fac) * (-n))
+          not found => error "discreteLog: ?? discrete logarithm"
+          -- end of shanks discrete logarithm algorithm
+          mult := mult * fac
+          disclog:=disclog+disc1
+          a:=a * (gen ** (-disc1))
+      disclog pretend NonNegativeInteger
+
+    discreteLog(logbase,b) ==
+      zero?(b) =>
+        messagePrint("discreteLog: logarithm of zero")$OutputForm
+        "failed"
+      zero?(logbase) =>
+        messagePrint("discreteLog: logarithm to base zero")$OutputForm
+        "failed"
+      b = logbase => 1
+      not zero?((groupord:=order(logbase)@PI) rem order(b)@PI) =>
+         messagePrint("discreteLog: second argument not in cyclic group _
+generated by first argument")$OutputForm
+         "failed"
+      faclist:=factors factor groupord
+      a:=b
+      disclog:Integer:=0
+      mult:Integer:=1
+      exp:Integer:= groupord
+      for f in faclist repeat
+        fac:=f.factor
+        primroot:= logbase ** (groupord quo fac)
+        for t in 0..f.exponent-1 repeat
+          exp:=exp quo fac
+          rhoHelp:= shanksDiscLogAlgorithm(primroot,_
+                a**exp,fac pretend NonNegativeInteger)$DLP($)
+          rhoHelp case "failed" => return "failed"
+          rho := (rhoHelp :: NNI) * mult
+          disclog := disclog + rho
+          mult := mult * fac
+          a:=a * (logbase ** (-rho))
+      disclog pretend NonNegativeInteger
+
+    FP ==> SparseUnivariatePolynomial($)
+    FRP ==> Factored FP
+    f,g:FP
+    squareFreePolynomial(f:FP):FRP ==
+          squareFree(f)$UnivariatePolynomialSquareFree($,FP)
+    factorPolynomial(f:FP):FRP == factor(f)$DistinctDegreeFactorize($,FP)
+    factorSquareFreePolynomial(f:FP):FRP ==
+        f = 0 => 0
+        flist := distdfact(f,true)$DistinctDegreeFactorize($,FP)
+        (flist.cont :: FP) *
+            (*/[primeFactor(u.irr,u.pow) for u in flist.factors])
+    gcdPolynomial(f:FP,g:FP):FP ==
+         gcd(f,g)$EuclideanDomain_&(FP)
+
+@
+\section{FFIELDC.lsp BOOTSTRAP}
+{\bf FFIELDC} depends on a chain of files. We need to break this cycle to build
+the algebra. So we keep a cached copy of the translated {\bf FFIELDC}
+category which we can write into the {\bf MID} directory. We compile 
+the lisp code and copy the {\bf FFIELDC.o} file to the {\bf OUT} directory.
+This is eventually forcibly replaced by a recompiled version. 
+
+Note that this code is not included in the generated catdef.spad file.
+
+<<FFIELDC.lsp BOOTSTRAP>>=
+
+(|/VERSIONCHECK| 2) 
+
+(SETQ |FiniteFieldCategory;AL| (QUOTE NIL)) 
+
+(DEFUN |FiniteFieldCategory| NIL (LET (#:G83129) (COND (|FiniteFieldCategory;AL|) (T (SETQ |FiniteFieldCategory;AL| (|FiniteFieldCategory;|)))))) 
+
+(DEFUN |FiniteFieldCategory;| NIL (PROG (#1=#:G83127) (RETURN (PROG1 (LETT #1# (|Join| (|FieldOfPrimeCharacteristic|) (|Finite|) (|StepThrough|) (|DifferentialRing|) (|mkCategory| (QUOTE |domain|) (QUOTE (((|charthRoot| (|$| |$|)) T) ((|conditionP| ((|Union| (|Vector| |$|) "failed") (|Matrix| |$|))) T) ((|factorsOfCyclicGroupSize| ((|List| (|Record| (|:| |factor| (|Integer|)) (|:| |exponent| (|Integer|)))))) T) ((|tableForDiscreteLogarithm| ((|Table| (|PositiveInteger|) (|NonNegativeInteger|)) (|Integer|))) T) ((|createPrimitiveElement| (|$|)) T) ((|primitiveElement| (|$|)) T) ((|primitive?| ((|Boolean|) |$|)) T) ((|discreteLog| ((|NonNegativeInteger|) |$|)) T) ((|order| ((|PositiveInteger|) |$|)) T) ((|representationType| ((|Union| "prime" "polynomial" "normal" "cyclic"))) T))) NIL (QUOTE ((|PositiveInteger|) (|NonNegativeInteger|) (|Boolean|) (|Table| (|PositiveInteger|) (|NonNegativeInteger|)) (|Integer|) (|List| (|Record| (|:| |factor| (|Integer|)) (|:| |exponent| (|Integer|)))) (|Matrix| |$|))) NIL)) |FiniteFieldCategory|) (SETELT #1# 0 (QUOTE (|FiniteFieldCategory|))))))) 
+
+(MAKEPROP (QUOTE |FiniteFieldCategory|) (QUOTE NILADIC) T) 
+@
+\section{FFIELDC-.lsp BOOTSTRAP}
+{\bf FFIELDC-} depends on {\bf FFIELDC}. We need to break this cycle to build
+the algebra. So we keep a cached copy of the translated {\bf FFIELDC-}
+category which we can write into the {\bf MID} directory. We compile 
+the lisp code and copy the {\bf FFIELDC-.o} file to the {\bf OUT} directory.
+This is eventually forcibly replaced by a recompiled version. 
+
+Note that this code is not included in the generated catdef.spad file.
+
+<<FFIELDC-.lsp BOOTSTRAP>>=
+
+(|/VERSIONCHECK| 2) 
+
+(DEFUN |FFIELDC-;differentiate;2S;1| (|x| |$|) (|spadConstant| |$| 7)) 
+
+(DEFUN |FFIELDC-;init;S;2| (|$|) (|spadConstant| |$| 7)) 
+
+(DEFUN |FFIELDC-;nextItem;SU;3| (|a| |$|) (COND ((SPADCALL (LETT |a| (SPADCALL (|+| (SPADCALL |a| (QREFELT |$| 11)) 1) (QREFELT |$| 12)) |FFIELDC-;nextItem;SU;3|) (QREFELT |$| 14)) (CONS 1 "failed")) ((QUOTE T) (CONS 0 |a|)))) 
+
+(DEFUN |FFIELDC-;order;SOpc;4| (|e| |$|) (SPADCALL (SPADCALL |e| (QREFELT |$| 17)) (QREFELT |$| 20))) 
+
+(DEFUN |FFIELDC-;conditionP;MU;5| (|mat| |$|) (PROG (|l|) (RETURN (SEQ (LETT |l| (SPADCALL |mat| (QREFELT |$| 24)) |FFIELDC-;conditionP;MU;5|) (COND ((OR (NULL |l|) (SPADCALL (ELT |$| 14) (|SPADfirst| |l|) (QREFELT |$| 27))) (EXIT (CONS 1 "failed")))) (EXIT (CONS 0 (SPADCALL (ELT |$| 28) (|SPADfirst| |l|) (QREFELT |$| 30)))))))) 
+
+(DEFUN |FFIELDC-;charthRoot;2S;6| (|x| |$|) (SPADCALL |x| (QUOTIENT2 (SPADCALL (QREFELT |$| 35)) (SPADCALL (QREFELT |$| 36))) (QREFELT |$| 37))) 
+
+(DEFUN |FFIELDC-;charthRoot;SU;7| (|x| |$|) (CONS 0 (SPADCALL |x| (QREFELT |$| 28)))) 
+
+(DEFUN |FFIELDC-;createPrimitiveElement;S;8| (|$|) (PROG (|sm1| |start| |i| #1=#:G83175 |e| |found|) (RETURN (SEQ (LETT |sm1| (|-| (SPADCALL (QREFELT |$| 35)) 1) |FFIELDC-;createPrimitiveElement;S;8|) (LETT |start| (COND ((SPADCALL (SPADCALL (QREFELT |$| 42)) (CONS 1 "polynomial") (QREFELT |$| 43)) (SPADCALL (QREFELT |$| 36))) ((QUOTE T) 1)) |FFIELDC-;createPrimitiveElement;S;8|) (LETT |found| (QUOTE NIL) |FFIELDC-;createPrimitiveElement;S;8|) (SEQ (LETT |i| |start| |FFIELDC-;createPrimitiveElement;S;8|) G190 (COND ((NULL (COND (|found| (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (LETT |e| (SPADCALL (PROG1 (LETT #1# |i| |FFIELDC-;createPrimitiveElement;S;8|) (|check-subtype| (|>| #1# 0) (QUOTE (|PositiveInteger|)) #1#)) (QREFELT |$| 12)) |FFIELDC-;createPrimitiveElement;S;8|) (EXIT (LETT |found| (EQL (SPADCALL |e| (QREFELT |$| 17)) |sm1|) |FFIELDC-;createPrimitiveElement;S;8|))) (LETT |i| (|+| |i| 1) |FFIELDC-;createPrimitiveElement;S;8|) (GO G190) G191 (EXIT NIL)) (EXIT |e|))))) 
+
+(DEFUN |FFIELDC-;primitive?;SB;9| (|a| |$|) (PROG (|explist| |q| |exp| #1=#:G83187 |equalone|) (RETURN (SEQ (COND ((SPADCALL |a| (QREFELT |$| 14)) (QUOTE NIL)) ((QUOTE T) (SEQ (LETT |explist| (SPADCALL (QREFELT |$| 47)) |FFIELDC-;primitive?;SB;9|) (LETT |q| (|-| (SPADCALL (QREFELT |$| 35)) 1) |FFIELDC-;primitive?;SB;9|) (LETT |equalone| (QUOTE NIL) |FFIELDC-;primitive?;SB;9|) (SEQ (LETT |exp| NIL |FFIELDC-;primitive?;SB;9|) (LETT #1# |explist| |FFIELDC-;primitive?;SB;9|) G190 (COND ((OR (ATOM #1#) (PROGN (LETT |exp| (CAR #1#) |FFIELDC-;primitive?;SB;9|) NIL) (NULL (COND (|equalone| (QUOTE NIL)) ((QUOTE T) (QUOTE T))))) (GO G191))) (SEQ (EXIT (LETT |equalone| (SPADCALL (SPADCALL |a| (QUOTIENT2 |q| (QCAR |exp|)) (QREFELT |$| 48)) (QREFELT |$| 49)) |FFIELDC-;primitive?;SB;9|))) (LETT #1# (CDR #1#) |FFIELDC-;primitive?;SB;9|) (GO G190) G191 (EXIT NIL)) (EXIT (COND (|equalone| (QUOTE NIL)) ((QUOTE T) (QUOTE T))))))))))) 
+
+(DEFUN |FFIELDC-;order;SPi;10| (|e| |$|) (PROG (|lof| |rec| #1=#:G83195 |primeDivisor| |j| #2=#:G83196 |a| |goon| |ord|) (RETURN (SEQ (COND ((SPADCALL |e| (|spadConstant| |$| 7) (QREFELT |$| 51)) (|error| "order(0) is not defined ")) ((QUOTE T) (SEQ (LETT |ord| (|-| (SPADCALL (QREFELT |$| 35)) 1) |FFIELDC-;order;SPi;10|) (LETT |a| 0 |FFIELDC-;order;SPi;10|) (LETT |lof| (SPADCALL (QREFELT |$| 47)) |FFIELDC-;order;SPi;10|) (SEQ (LETT |rec| NIL |FFIELDC-;order;SPi;10|) (LETT #1# |lof| |FFIELDC-;order;SPi;10|) G190 (COND ((OR (ATOM #1#) (PROGN (LETT |rec| (CAR #1#) |FFIELDC-;order;SPi;10|) NIL)) (GO G191))) (SEQ (LETT |a| (QUOTIENT2 |ord| (LETT |primeDivisor| (QCAR |rec|) |FFIELDC-;order;SPi;10|)) |FFIELDC-;order;SPi;10|) (LETT |goon| (SPADCALL (SPADCALL |e| |a| (QREFELT |$| 48)) (QREFELT |$| 49)) |FFIELDC-;order;SPi;10|) (SEQ (LETT |j| 0 |FFIELDC-;order;SPi;10|) (LETT #2# (|-| (QCDR |rec|) 2) |FFIELDC-;order;SPi;10|) G190 (COND ((OR (QSGREATERP |j| #2#) (NULL |goon|)) (GO G191))) (SEQ (LETT |ord| |a| |FFIELDC-;order;SPi;10|) (LETT |a| (QUOTIENT2 |ord| |primeDivisor|) |FFIELDC-;order;SPi;10|) (EXIT (LETT |goon| (SPADCALL (SPADCALL |e| |a| (QREFELT |$| 48)) (QREFELT |$| 49)) |FFIELDC-;order;SPi;10|))) (LETT |j| (QSADD1 |j|) |FFIELDC-;order;SPi;10|) (GO G190) G191 (EXIT NIL)) (EXIT (COND (|goon| (LETT |ord| |a| |FFIELDC-;order;SPi;10|))))) (LETT #1# (CDR #1#) |FFIELDC-;order;SPi;10|) (GO G190) G191 (EXIT NIL)) (EXIT |ord|)))))))) 
+
+(DEFUN |FFIELDC-;discreteLog;SNni;11| (|b| |$|) (PROG (|faclist| |gen| |groupord| |f| #1=#:G83216 |fac| |t| #2=#:G83217 |exp| |exptable| |n| |end| |i| |rho| |found| |disc1| |c| |mult| |disclog| |a|) (RETURN (SEQ (COND ((SPADCALL |b| (QREFELT |$| 14)) (|error| "discreteLog: logarithm of zero")) ((QUOTE T) (SEQ (LETT |faclist| (SPADCALL (QREFELT |$| 47)) |FFIELDC-;discreteLog;SNni;11|) (LETT |a| |b| |FFIELDC-;discreteLog;SNni;11|) (LETT |gen| (SPADCALL (QREFELT |$| 53)) |FFIELDC-;discreteLog;SNni;11|) (EXIT (COND ((SPADCALL |b| |gen| (QREFELT |$| 51)) 1) ((QUOTE T) (SEQ (LETT |disclog| 0 |FFIELDC-;discreteLog;SNni;11|) (LETT |mult| 1 |FFIELDC-;discreteLog;SNni;11|) (LETT |groupord| (|-| (SPADCALL (QREFELT |$| 35)) 1) |FFIELDC-;discreteLog;SNni;11|) (LETT |exp| |groupord| |FFIELDC-;discreteLog;SNni;11|) (SEQ (LETT |f| NIL |FFIELDC-;discreteLog;SNni;11|) (LETT #1# |faclist| |FFIELDC-;discreteLog;SNni;11|) G190 (COND ((OR (ATOM #1#) (PROGN (LETT |f| (CAR #1#) |FFIELDC-;discreteLog;SNni;11|) NIL)) (GO G191))) (SEQ (LETT |fac| (QCAR |f|) |FFIELDC-;discreteLog;SNni;11|) (EXIT (SEQ (LETT |t| 0 |FFIELDC-;discreteLog;SNni;11|) (LETT #2# (|-| (QCDR |f|) 1) |FFIELDC-;discreteLog;SNni;11|) G190 (COND ((QSGREATERP |t| #2#) (GO G191))) (SEQ (LETT |exp| (QUOTIENT2 |exp| |fac|) |FFIELDC-;discreteLog;SNni;11|) (LETT |exptable| (SPADCALL |fac| (QREFELT |$| 55)) |FFIELDC-;discreteLog;SNni;11|) (LETT |n| (SPADCALL |exptable| (QREFELT |$| 56)) |FFIELDC-;discreteLog;SNni;11|) (LETT |c| (SPADCALL |a| |exp| (QREFELT |$| 48)) |FFIELDC-;discreteLog;SNni;11|) (LETT |end| (QUOTIENT2 (|-| |fac| 1) |n|) |FFIELDC-;discreteLog;SNni;11|) (LETT |found| (QUOTE NIL) |FFIELDC-;discreteLog;SNni;11|) (LETT |disc1| 0 |FFIELDC-;discreteLog;SNni;11|) (SEQ (LETT |i| 0 |FFIELDC-;discreteLog;SNni;11|) G190 (COND ((OR (QSGREATERP |i| |end|) (NULL (COND (|found| (QUOTE NIL)) ((QUOTE T) (QUOTE T))))) (GO G191))) (SEQ (LETT |rho| (SPADCALL (SPADCALL |c| (QREFELT |$| 11)) |exptable| (QREFELT |$| 58)) |FFIELDC-;discreteLog;SNni;11|) (EXIT (COND ((QEQCAR |rho| 0) (SEQ (LETT |found| (QUOTE T) |FFIELDC-;discreteLog;SNni;11|) (EXIT (LETT |disc1| (|*| (|+| (|*| |n| |i|) (QCDR |rho|)) |mult|) |FFIELDC-;discreteLog;SNni;11|)))) ((QUOTE T) (LETT |c| (SPADCALL |c| (SPADCALL |gen| (|*| (QUOTIENT2 |groupord| |fac|) (|-| |n|)) (QREFELT |$| 48)) (QREFELT |$| 59)) |FFIELDC-;discreteLog;SNni;11|))))) (LETT |i| (QSADD1 |i|) |FFIELDC-;discreteLog;SNni;11|) (GO G190) G191 (EXIT NIL)) (EXIT (COND (|found| (SEQ (LETT |mult| (|*| |mult| |fac|) |FFIELDC-;discreteLog;SNni;11|) (LETT |disclog| (|+| |disclog| |disc1|) |FFIELDC-;discreteLog;SNni;11|) (EXIT (LETT |a| (SPADCALL |a| (SPADCALL |gen| (|-| |disc1|) (QREFELT |$| 48)) (QREFELT |$| 59)) |FFIELDC-;discreteLog;SNni;11|)))) ((QUOTE T) (|error| "discreteLog: ?? discrete logarithm"))))) (LETT |t| (QSADD1 |t|) |FFIELDC-;discreteLog;SNni;11|) (GO G190) G191 (EXIT NIL)))) (LETT #1# (CDR #1#) |FFIELDC-;discreteLog;SNni;11|) (GO G190) G191 (EXIT NIL)) (EXIT |disclog|)))))))))))) 
+
+(DEFUN |FFIELDC-;discreteLog;2SU;12| (|logbase| |b| |$|) (PROG (|groupord| |faclist| |f| #1=#:G83235 |fac| |primroot| |t| #2=#:G83236 |exp| |rhoHelp| #3=#:G83234 |rho| |disclog| |mult| |a|) (RETURN (SEQ (EXIT (COND ((SPADCALL |b| (QREFELT |$| 14)) (SEQ (SPADCALL "discreteLog: logarithm of zero" (QREFELT |$| 64)) (EXIT (CONS 1 "failed")))) ((SPADCALL |logbase| (QREFELT |$| 14)) (SEQ (SPADCALL "discreteLog: logarithm to base zero" (QREFELT |$| 64)) (EXIT (CONS 1 "failed")))) ((SPADCALL |b| |logbase| (QREFELT |$| 51)) (CONS 0 1)) ((QUOTE T) (COND ((NULL (ZEROP (REMAINDER2 (LETT |groupord| (SPADCALL |logbase| (QREFELT |$| 17)) |FFIELDC-;discreteLog;2SU;12|) (SPADCALL |b| (QREFELT |$| 17))))) (SEQ (SPADCALL "discreteLog: second argument not in cyclic group generated by first argument" (QREFELT |$| 64)) (EXIT (CONS 1 "failed")))) ((QUOTE T) (SEQ (LETT |faclist| (SPADCALL (SPADCALL |groupord| (QREFELT |$| 66)) (QREFELT |$| 68)) |FFIELDC-;discreteLog;2SU;12|) (LETT |a| |b| |FFIELDC-;discreteLog;2SU;12|) (LETT |disclog| 0 |FFIELDC-;discreteLog;2SU;12|) (LETT |mult| 1 |FFIELDC-;discreteLog;2SU;12|) (LETT |exp| |groupord| |FFIELDC-;discreteLog;2SU;12|) (SEQ (LETT |f| NIL |FFIELDC-;discreteLog;2SU;12|) (LETT #1# |faclist| |FFIELDC-;discreteLog;2SU;12|) G190 (COND ((OR (ATOM #1#) (PROGN (LETT |f| (CAR #1#) |FFIELDC-;discreteLog;2SU;12|) NIL)) (GO G191))) (SEQ (LETT |fac| (QCAR |f|) |FFIELDC-;discreteLog;2SU;12|) (LETT |primroot| (SPADCALL |logbase| (QUOTIENT2 |groupord| |fac|) (QREFELT |$| 48)) |FFIELDC-;discreteLog;2SU;12|) (EXIT (SEQ (LETT |t| 0 |FFIELDC-;discreteLog;2SU;12|) (LETT #2# (|-| (QCDR |f|) 1) |FFIELDC-;discreteLog;2SU;12|) G190 (COND ((QSGREATERP |t| #2#) (GO G191))) (SEQ (LETT |exp| (QUOTIENT2 |exp| |fac|) |FFIELDC-;discreteLog;2SU;12|) (LETT |rhoHelp| (SPADCALL |primroot| (SPADCALL |a| |exp| (QREFELT |$| 48)) |fac| (QREFELT |$| 70)) |FFIELDC-;discreteLog;2SU;12|) (EXIT (COND ((QEQCAR |rhoHelp| 1) (PROGN (LETT #3# (CONS 1 "failed") |FFIELDC-;discreteLog;2SU;12|) (GO #3#))) ((QUOTE T) (SEQ (LETT |rho| (|*| (QCDR |rhoHelp|) |mult|) |FFIELDC-;discreteLog;2SU;12|) (LETT |disclog| (|+| |disclog| |rho|) |FFIELDC-;discreteLog;2SU;12|) (LETT |mult| (|*| |mult| |fac|) |FFIELDC-;discreteLog;2SU;12|) (EXIT (LETT |a| (SPADCALL |a| (SPADCALL |logbase| (|-| |rho|) (QREFELT |$| 48)) (QREFELT |$| 59)) |FFIELDC-;discreteLog;2SU;12|))))))) (LETT |t| (QSADD1 |t|) |FFIELDC-;discreteLog;2SU;12|) (GO G190) G191 (EXIT NIL)))) (LETT #1# (CDR #1#) |FFIELDC-;discreteLog;2SU;12|) (GO G190) G191 (EXIT NIL)) (EXIT (CONS 0 |disclog|)))))))) #3# (EXIT #3#))))) 
+
+(DEFUN |FFIELDC-;squareFreePolynomial| (|f| |$|) (SPADCALL |f| (QREFELT |$| 75))) 
+
+(DEFUN |FFIELDC-;factorPolynomial| (|f| |$|) (SPADCALL |f| (QREFELT |$| 77))) 
+
+(DEFUN |FFIELDC-;factorSquareFreePolynomial| (|f| |$|) (PROG (|flist| |u| #1=#:G83248 #2=#:G83245 #3=#:G83243 #4=#:G83244) (RETURN (SEQ (COND ((SPADCALL |f| (|spadConstant| |$| 78) (QREFELT |$| 79)) (|spadConstant| |$| 80)) ((QUOTE T) (SEQ (LETT |flist| (SPADCALL |f| (QUOTE T) (QREFELT |$| 83)) |FFIELDC-;factorSquareFreePolynomial|) (EXIT (SPADCALL (SPADCALL (QCAR |flist|) (QREFELT |$| 84)) (PROGN (LETT #4# NIL |FFIELDC-;factorSquareFreePolynomial|) (SEQ (LETT |u| NIL |FFIELDC-;factorSquareFreePolynomial|) (LETT #1# (QCDR |flist|) |FFIELDC-;factorSquareFreePolynomial|) G190 (COND ((OR (ATOM #1#) (PROGN (LETT |u| (CAR #1#) |FFIELDC-;factorSquareFreePolynomial|) NIL)) (GO G191))) (SEQ (EXIT (PROGN (LETT #2# (SPADCALL (QCAR |u|) (QCDR |u|) (QREFELT |$| 85)) |FFIELDC-;factorSquareFreePolynomial|) (COND (#4# (LETT #3# (SPADCALL #3# #2# (QREFELT |$| 86)) |FFIELDC-;factorSquareFreePolynomial|)) ((QUOTE T) (PROGN (LETT #3# #2# |FFIELDC-;factorSquareFreePolynomial|) (LETT #4# (QUOTE T) |FFIELDC-;factorSquareFreePolynomial|))))))) (LETT #1# (CDR #1#) |FFIELDC-;factorSquareFreePolynomial|) (GO G190) G191 (EXIT NIL)) (COND (#4# #3#) ((QUOTE T) (|spadConstant| |$| 87)))) (QREFELT |$| 88)))))))))) 
+
+(DEFUN |FFIELDC-;gcdPolynomial;3Sup;16| (|f| |g| |$|) (SPADCALL |f| |g| (QREFELT |$| 90))) 
+
+(DEFUN |FiniteFieldCategory&| (|#1|) (PROG (|DV$1| |dv$| |$| |pv$|) (RETURN (PROGN (LETT |DV$1| (|devaluate| |#1|) . #1=(|FiniteFieldCategory&|)) (LETT |dv$| (LIST (QUOTE |FiniteFieldCategory&|) |DV$1|) . #1#) (LETT |$| (GETREFV 93) . #1#) (QSETREFV |$| 0 |dv$|) (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 NIL) . #1#)) (|stuffDomainSlots| |$|) (QSETREFV |$| 6 |#1|) |$|)))) 
+
+(MAKEPROP (QUOTE |FiniteFieldCategory&|) (QUOTE |infovec|) (LIST (QUOTE #(NIL NIL NIL NIL NIL NIL (|local| |#1|) (0 . |Zero|) |FFIELDC-;differentiate;2S;1| |FFIELDC-;init;S;2| (|PositiveInteger|) (4 . |lookup|) (9 . |index|) (|Boolean|) (14 . |zero?|) (|Union| |$| (QUOTE "failed")) |FFIELDC-;nextItem;SU;3| (19 . |order|) (|Integer|) (|OnePointCompletion| 10) (24 . |coerce|) |FFIELDC-;order;SOpc;4| (|List| 26) (|Matrix| 6) (29 . |nullSpace|) (|Mapping| 13 6) (|Vector| 6) (34 . |every?|) (40 . |charthRoot|) (|Mapping| 6 6) (45 . |map|) (|Union| (|Vector| |$|) (QUOTE "failed")) (|Matrix| |$|) |FFIELDC-;conditionP;MU;5| (|NonNegativeInteger|) (51 . |size|) (55 . |characteristic|) (59 . |**|) |FFIELDC-;charthRoot;2S;6| |FFIELDC-;charthRoot;SU;7| (65 . |One|) (|Union| (QUOTE "prime") (QUOTE "polynomial") (QUOTE "normal") (QUOTE "cyclic")) (69 . |representationType|) (73 . |=|) |FFIELDC-;createPrimitiveElement;S;8| (|Record| (|:| |factor| 18) (|:| |exponent| 18)) (|List| 45) (79 . |factorsOfCyclicGroupSize|) (83 . |**|) (89 . |one?|) |FFIELDC-;primitive?;SB;9| (94 . |=|) |FFIELDC-;order;SPi;10| (100 . |primitiveElement|) (|Table| 10 34) (104 . |tableForDiscreteLogarithm|) (109 . |#|) (|Union| 34 (QUOTE "failed")) (114 . |search|) (120 . |*|) |FFIELDC-;discreteLog;SNni;11| (|Void|) (|String|) (|OutputForm|) (126 . |messagePrint|) (|Factored| |$|) (131 . |factor|) (|Factored| 18) (136 . |factors|) (|DiscreteLogarithmPackage| 6) (141 . |shanksDiscLogAlgorithm|) |FFIELDC-;discreteLog;2SU;12| (|Factored| 73) (|SparseUnivariatePolynomial| 6) (|UnivariatePolynomialSquareFree| 6 73) (148 . |squareFree|) (|DistinctDegreeFactorize| 6 73) (153 . |factor|) (158 . |Zero|) (162 . |=|) (168 . |Zero|) (|Record| (|:| |irr| 73) (|:| |pow| 18)) (|Record| (|:| |cont| 6) (|:| |factors| (|List| 81))) (172 . |distdfact|) (178 . |coerce|) (183 . |primeFactor|) (189 . |*|) (195 . |One|) (199 . |*|) (|EuclideanDomain&| 73) (205 . |gcd|) (|SparseUnivariatePolynomial| |$|) |FFIELDC-;gcdPolynomial;3Sup;16|)) (QUOTE #(|primitive?| 211 |order| 216 |nextItem| 226 |init| 231 |gcdPolynomial| 235 |discreteLog| 241 |differentiate| 252 |createPrimitiveElement| 257 |conditionP| 261 |charthRoot| 266)) (QUOTE NIL) (CONS (|makeByteWordVec2| 1 (QUOTE NIL)) (CONS (QUOTE #()) (CONS (QUOTE #()) (|makeByteWordVec2| 92 (QUOTE (0 6 0 7 1 6 10 0 11 1 6 0 10 12 1 6 13 0 14 1 6 10 0 17 1 19 0 18 20 1 23 22 0 24 2 26 13 25 0 27 1 6 0 0 28 2 26 0 29 0 30 0 6 34 35 0 6 34 36 2 6 0 0 34 37 0 6 0 40 0 6 41 42 2 41 13 0 0 43 0 6 46 47 2 6 0 0 18 48 1 6 13 0 49 2 6 13 0 0 51 0 6 0 53 1 6 54 18 55 1 54 34 0 56 2 54 57 10 0 58 2 6 0 0 0 59 1 63 61 62 64 1 18 65 0 66 1 67 46 0 68 3 69 57 6 6 34 70 1 74 72 73 75 1 76 72 73 77 0 73 0 78 2 73 13 0 0 79 0 72 0 80 2 76 82 73 13 83 1 73 0 6 84 2 72 0 73 18 85 2 72 0 0 0 86 0 72 0 87 2 72 0 73 0 88 2 89 0 0 0 90 1 0 13 0 50 1 0 10 0 52 1 0 19 0 21 1 0 15 0 16 0 0 0 9 2 0 91 91 91 92 1 0 34 0 60 2 0 57 0 0 71 1 0 0 0 8 0 0 0 44 1 0 31 32 33 1 0 0 0 38 1 0 15 0 39)))))) (QUOTE |lookupComplete|))) 
+@
+\section{package FFSLPE FiniteFieldSolveLinearPolynomialEquation}
+<<package FFSLPE FiniteFieldSolveLinearPolynomialEquation>>=
+)abbrev package FFSLPE FiniteFieldSolveLinearPolynomialEquation
+++ Author: Davenport
+++ Date Created: 1991
+++ Date Last Updated:
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++ This package solves linear diophantine equations for Bivariate polynomials
+++ over finite fields
+
+FiniteFieldSolveLinearPolynomialEquation(F:FiniteFieldCategory,
+                                        FP:UnivariatePolynomialCategory F,
+                                        FPP:UnivariatePolynomialCategory FP): with
+   solveLinearPolynomialEquation: (List FPP, FPP) -> Union(List FPP,"failed")
+              ++ solveLinearPolynomialEquation([f1, ..., fn], g)
+              ++ (where the fi are relatively prime to each other)
+              ++ returns a list of ai such that
+              ++ \spad{g/prod fi = sum ai/fi}
+              ++ or returns "failed" if no such list of ai's exists.
+  == add
+     oldlp:List FPP := []
+     slpePrime: FP := monomial(1,1)
+     oldtable:Vector List FPP := []
+     lp: List FPP
+     p: FPP
+     import DistinctDegreeFactorize(F,FP)
+     solveLinearPolynomialEquation(lp,p) ==
+       if (oldlp ^= lp) then
+          -- we have to generate a new table
+          deg:= +/[degree u for u in lp]
+          ans:Union(Vector List FPP,"failed"):="failed"
+          slpePrime:=monomial(1,1)+monomial(1,0)   -- x+1: our starting guess
+          while (ans case "failed") repeat
+            ans:=tablePow(deg,slpePrime,lp)$GenExEuclid(FP,FPP)
+            if (ans case "failed") then
+               slpePrime:= nextItem(slpePrime)::FP
+               while (degree slpePrime > 1) and
+                     not irreducible? slpePrime repeat
+                 slpePrime := nextItem(slpePrime)::FP
+          oldtable:=(ans:: Vector List FPP)
+       answer:=solveid(p,slpePrime,oldtable)
+       answer
+
+@
+\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 DLP DiscreteLogarithmPackage>>
+<<category FPC FieldOfPrimeCharacteristic>>
+<<category XF ExtensionField>>
+<<category FAXF FiniteAlgebraicExtensionField>>
+<<category FFIELDC FiniteFieldCategory>>
+<<package FFSLPE FiniteFieldSolveLinearPolynomialEquation>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}