Initial population.

1 files changed, 431 insertions, 0 deletions

diff --git a/src/algebra/ffhom.spad.pamphlet b/src/algebra/ffhom.spad.pamphlet
new file mode 100644
index 00000000..50bf7ef1
--- /dev/null
+++ b/src/algebra/ffhom.spad.pamphlet
@@ -0,0 +1,431 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra ffhom.spad}
+\author{Johannes Grabmeier, Alfred Scheerhorn}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\begin{verbatim}
+-- 28.01.93: AS and JG: setting of init? flag in
+--    functions initialize put at the
+--    end to avoid errors with interruption.
+-- 12.05.92 JG: long lines
+-- 17.02.92 AS: convertWRTdifferentDefPol12 and convertWRTdifferentDefPol21
+--              simplified. 
+-- 17.02.92 AS: initialize() modified set up of basis change
+--              matrices between normal and polynomial rep.
+--              New version uses reducedQPowers and is more efficient.
+-- 24.07.92 JG: error messages improved
+\end{verbatim}
+\section{package FFHOM FiniteFieldHomomorphisms}
+<<package FFHOM FiniteFieldHomomorphisms>>=
+)abbrev package FFHOM FiniteFieldHomomorphisms
+++ Authors: J.Grabmeier, A.Scheerhorn
+++ Date Created: 26.03.1991
+++ Date Last Updated:
+++ Basic Operations:
+++ Related Constructors: FiniteFieldCategory, FiniteAlgebraicExtensionField
+++ Also See:
+++ AMS Classifications:
+++ Keywords: finite field, homomorphism, isomorphism
+++ 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:
+++  FiniteFieldHomomorphisms(F1,GF,F2) exports coercion functions of
+++  elements between the fields {\em F1} and {\em F2}, which both must be
+++  finite simple algebraic extensions of the finite ground field {\em GF}.
+FiniteFieldHomomorphisms(F1,GF,F2): Exports == Implementation where
+  F1: FiniteAlgebraicExtensionField(GF)
+  GF: FiniteFieldCategory
+  F2: FiniteAlgebraicExtensionField(GF)
+ -- the homorphism can only convert elements w.r.t. the last extension .
+  -- Adding a function 'groundField()' which returns the groundfield of GF
+  -- as a variable of type FiniteFieldCategory in the new compiler, one
+  -- could build up 'convert' recursively to get an homomorphism w.r.t
+  -- the whole extension.
+ 
+  I   ==> Integer
+  NNI ==> NonNegativeInteger
+  SI  ==> SingleInteger
+  PI  ==> PositiveInteger
+  SUP ==> SparseUnivariatePolynomial
+  M   ==> Matrix GF
+  FFP ==> FiniteFieldExtensionByPolynomial
+  FFPOL2 ==> FiniteFieldPolynomialPackage2
+  FFPOLY ==> FiniteFieldPolynomialPackage
+  OUT ==> OutputForm
+ 
+  Exports ==> with
+ 
+    coerce: F1  ->  F2
+      ++ coerce(x) is the homomorphic image of x from
+      ++ {\em F1} in {\em F2}. Thus {\em coerce} is a
+      ++ field homomorphism between the fields extensions
+      ++ {\em F1} and {\em F2} both over ground field {\em GF} 
+      ++ (the second argument to the package).
+      ++ Error: if the extension degree of {\em F1} doesn't divide
+      ++ the extension degree of {\em F2}.
+      ++ Note that the other coercion function in the 
+      ++ \spadtype{FiniteFieldHomomorphisms} is a left inverse.
+ 
+    coerce: F2  ->  F1
+      ++ coerce(x) is the homomorphic image of x from
+      ++ {\em F2} in {\em F1}, where {\em coerce} is a
+      ++ field homomorphism between the fields extensions
+      ++ {\em F2} and {\em F1} both over ground field {\em GF}
+      ++ (the second argument to the package).
+      ++ Error: if the extension degree of {\em F2} doesn't divide
+      ++ the extension degree of {\em F1}.
+      ++ Note that the other coercion function in the 
+      ++ \spadtype{FiniteFieldHomomorphisms} is a left inverse.
+    -- coerce(coerce(x:F1)@F2)@F1 = x and coerce(coerce(y:F2)@F1)@F2 = y
+ 
+  Implementation ==> add
+ 
+-- global variables ===================================================
+ 
+    degree1:NNI:= extensionDegree()$F1
+    degree2:NNI:= extensionDegree()$F2
+    -- the degrees of the last extension
+ 
+    -- a necessary condition for the one field being an subfield of
+    -- the other one is, that the respective extension degrees are
+    -- multiples
+    if max(degree1,degree2) rem min(degree1,degree2) ^= 0 then
+      error "FFHOM: one extension degree must divide the other one"
+ 
+    conMat1to2:M:= zero(degree2,degree1)$M
+    -- conversion Matix for the conversion direction F1 -> F2
+    conMat2to1:M:= zero(degree1,degree2)$M
+    -- conversion Matix for the conversion direction F2 -> F1
+ 
+    repType1:=representationType()$F1
+    repType2:=representationType()$F2
+    -- the representation types of the fields
+ 
+    init?:Boolean:=true
+    -- gets false after initialization
+ 
+    defPol1:=definingPolynomial()$F1
+    defPol2:=definingPolynomial()$F2
+    -- the defining polynomials of the fields
+ 
+ 
+-- functions ==========================================================
+ 
+ 
+    compare: (SUP GF,SUP GF) -> Boolean
+    -- compares two polynomials
+ 
+    convertWRTsameDefPol12: F1  ->  F2
+    convertWRTsameDefPol21: F2  ->  F1
+    -- homomorphism if the last extension of F1 and F2 was build up
+    -- using the same defining polynomials
+ 
+    convertWRTdifferentDefPol12: F1  ->  F2
+    convertWRTdifferentDefPol21: F2  ->  F1
+    -- homomorphism if the last extension of F1 and F2 was build up
+    -- with different defining polynomials
+ 
+    initialize: () -> Void
+    -- computes the conversion matrices
+ 
+    compare(g:(SUP GF),f:(SUP GF)) ==
+      degree(f)$(SUP GF)  >$NNI degree(g)$(SUP GF) => true
+      degree(f)$(SUP GF) <$NNI degree(g)$(SUP GF) => false
+      equal:Integer:=0
+      for i in degree(f)$(SUP GF)..0 by -1 while equal=0 repeat
+        not zero?(coefficient(f,i)$(SUP GF))$GF and _
+             zero?(coefficient(g,i)$(SUP GF))$GF => equal:=1
+        not zero?(coefficient(g,i)$(SUP GF))$GF and _
+             zero?(coefficient(f,i)$(SUP GF))$GF => equal:=(-1)
+        (f1:=lookup(coefficient(f,i)$(SUP GF))$GF) >$PositiveInteger _
+         (g1:=lookup(coefficient(g,i)$(SUP GF))$GF) =>  equal:=1
+        f1 <$PositiveInteger g1 => equal:=(-1)
+      equal=1 => true
+      false
+ 
+    initialize() ==
+      -- 1) in the case of equal def. polynomials initialize is called only
+      --  if one of the rep. types is "normal" and the other one is "polynomial"
+      --  we have to compute the basis change matrix 'mat', which i-th
+      --  column are the coordinates of a**(q**i), the i-th component of
+      --  the normal basis ('a' the root of the def. polynomial and q the
+      --  size of the groundfield)
+      defPol1 =$(SUP GF) defPol2 =>
+        -- new code using reducedQPowers
+        mat:=zero(degree1,degree1)$M
+        arr:=reducedQPowers(defPol1)$FFPOLY(GF)
+        for i in 1..degree1 repeat
+          setColumn_!(mat,i,vectorise(arr.(i-1),degree1)$SUP(GF))$M
+          -- old code
+          -- here one of the representation types must be "normal"
+          --a:=basis()$FFP(GF,defPol1).2  -- the root of the def. polynomial
+          --setColumn_!(mat,1,coordinates(a)$FFP(GF,defPol1))$M
+          --for i in 2..degree1 repeat
+          --  a:= a **$FFP(GF,defPol1) size()$GF
+          --  setColumn_!(mat,i,coordinates(a)$FFP(GF,defPol1))$M
+          --for the direction "normal" -> "polynomial" we have to multiply the
+          -- coordinate vector of an element of the normal basis field with
+          -- the matrix 'mat'. In this case 'mat' is the correct conversion
+          -- matrix for the conversion of F1 to F2, its inverse the correct
+          -- inversion matrix for the conversion of F2 to F1
+        repType1 = "normal" =>  -- repType2 = "polynomial"
+          conMat1to2:=copy(mat)
+          conMat2to1:=copy(inverse(mat)$M :: M)
+          --we finish the function for one case, hence reset initialization flag
+          init? := false
+          void()$Void
+          -- print("'normal' <=> 'polynomial' matrices initialized"::OUT)
+        -- in the other case we have to change the matrices
+        -- repType2 = "normal" and repType1 = "polynomial"
+        conMat2to1:=copy(mat)
+        conMat1to2:=copy(inverse(mat)$M :: M)
+        -- print("'normal' <=> 'polynomial' matrices initialized"::OUT)
+        --we finish the function for one case, hence reset initialization flag
+        init? := false
+        void()$Void
+      -- 2) in the case of different def. polynomials we have to order the
+      --    fields to get the same isomorphism, if the package is called with
+      --    the fields F1 and F2 swapped.
+      dPbig:= defPol2
+      rTbig:= repType2
+      dPsmall:= defPol1
+      rTsmall:= repType1
+      degbig:=degree2
+      degsmall:=degree1
+      if compare(defPol2,defPol1) then
+        degsmall:=degree2
+        degbig:=degree1
+        dPbig:= defPol1
+        rTbig:= repType1
+        dPsmall:= defPol2
+        rTsmall:= repType2
+      -- 3) in every case we need a conversion between the polynomial
+      --  represented fields. Therefore we compute 'root' as a root of the
+      --  'smaller' def. polynomial in the 'bigger' field.
+      --  We compute the matrix 'matsb', which i-th column are the coordinates
+      --  of the (i-1)-th power of root, i=1..degsmall. Multiplying a
+      --  coordinate vector of an element of the 'smaller' field by this
+      --  matrix, we got the coordinates of the corresponding element in the
+      --  'bigger' field.
+      -- compute the root of dPsmall in the 'big' field
+      root:=rootOfIrreduciblePoly(dPsmall)$FFPOL2(FFP(GF,dPbig),GF)
+      -- set up matrix for polynomial conversion
+      matsb:=zero(degbig,degsmall)$M
+      qsetelt_!(matsb,1,1,1$GF)$M
+      a:=root
+      for i in 2..degsmall repeat
+        setColumn_!(matsb,i,coordinates(a)$FFP(GF,dPbig))$M
+        a := a *$FFP(GF,dPbig) root
+      --  the conversion from 'big' to 'small': we can't invert matsb
+      --  directly, because it has degbig rows and degsmall columns and
+      --  may be no square matrix. Therfore we construct a square matrix
+      --  mat from degsmall linear independent rows of matsb and invert it.
+      --  Now we get the conversion matrix 'matbs' for the conversion from
+      --  'big' to 'small' by putting the columns of mat at the indices
+      --  of the linear independent rows of matsb to columns of matbs.
+      ra:I:=1   -- the rank
+      mat:M:=transpose(row(matsb,1))$M -- has already rank 1
+      rowind:I:=2
+      iVec:Vector I:=new(degsmall,1$I)$(Vector I)
+      while ra < degsmall repeat
+        if rank(vertConcat(mat,transpose(row(matsb,rowind))$M)$M)$M > ra then
+          mat:=vertConcat(mat,transpose(row(matsb,rowind))$M)$M
+          ra:=ra+1
+          iVec.ra := rowind
+        rowind:=rowind + 1
+      mat:=inverse(mat)$M :: M
+      matbs:=zero(degsmall,degbig)$M
+      for i in 1..degsmall repeat
+        setColumn_!(matbs,iVec.i,column(mat,i)$M)$M
+      -- print(matsb::OUT)
+      -- print(matbs::OUT)
+      -- 4) if the 'bigger' field is "normal" we have to compose the
+      --  polynomial conversion with a conversion from polynomial to normal
+      --  between the FFP(GF,dPbig) and FFNBP(GF,dPbig) the 'bigger'
+      --  field. Therefore we compute a conversion matrix 'mat' as in 1)
+      --  Multiplying with the inverse of 'mat' yields the desired
+      --  conversion from polynomial to normal. Multiplying this matrix by
+      --  the above computed 'matsb' we got the matrix for converting form
+      --  'small polynomial' to 'big normal'.
+      -- set up matrix 'mat' for polynomial to normal
+      if rTbig = "normal" then
+        arr:=reducedQPowers(dPbig)$FFPOLY(GF)
+        mat:=zero(degbig,degbig)$M
+        for i in 1..degbig repeat
+          setColumn_!(mat,i,vectorise(arr.(i-1),degbig)$SUP(GF))$M
+        -- old code
+        --a:=basis()$FFP(GF,dPbig).2  -- the root of the def.Polynomial
+        --setColumn_!(mat,1,coordinates(a)$FFP(GF,dPbig))$M
+        --for i in 2..degbig repeat
+        --  a:= a **$FFP(GF,dPbig) size()$GF
+        --  setColumn_!(mat,i,coordinates(a)$FFP(GF,dPbig))$M
+        -- print(inverse(mat)$M::OUT)
+        matsb:= (inverse(mat)$M :: M) * matsb
+        -- print("inv *.."::OUT)
+        matbs:=matbs * mat
+        -- 5) if the 'smaller' field is "normal" we have first to convert
+        --    from 'small normal' to 'small polynomial', that is from
+        --    FFNBP(GF,dPsmall) to FFP(GF,dPsmall). Therefore we compute a
+        --    conversion matrix 'mat' as in 1). Multiplying with  'mat'
+        --    yields the desired conversion from normal to polynomial.
+        --    Multiplying the above computed 'matsb' with 'mat' we got the
+        --    matrix for converting form 'small normal' to 'big normal'.
+      -- set up matrix 'mat' for normal to polynomial
+      if rTsmall = "normal" then
+        arr:=reducedQPowers(dPsmall)$FFPOLY(GF)
+        mat:=zero(degsmall,degsmall)$M
+        for i in 1..degsmall repeat
+          setColumn_!(mat,i,vectorise(arr.(i-1),degsmall)$SUP(GF))$M
+      -- old code
+      --b:FFP(GF,dPsmall):=basis()$FFP(GF,dPsmall).2
+      --setColumn_!(mat,1,coordinates(b)$FFP(GF,dPsmall))$M
+      --for i in 2..degsmall repeat
+      --  b:= b **$FFP(GF,dPsmall) size()$GF
+      --  setColumn_!(mat,i,coordinates(b)$FFP(GF,dPsmall))$M
+        -- print(mat::OUT)
+        matsb:= matsb * mat
+        matbs:= (inverse(mat) :: M) * matbs
+      -- now 'matsb' is the corret conversion matrix for 'small' to 'big'
+      -- and 'matbs' the corret one for 'big' to 'small'.
+      -- depending on the above ordering the conversion matrices are
+      -- initialized
+      dPbig =$(SUP GF) defPol2 =>
+        conMat1to2 :=matsb
+        conMat2to1 :=matbs
+        -- print(conMat1to2::OUT)
+        -- print(conMat2to1::OUT)
+        -- print("conversion matrices initialized"::OUT)
+        --we finish the function for one case, hence reset initialization flag
+        init? := false
+        void()$Void
+      conMat1to2 :=matbs
+      conMat2to1 :=matsb
+      -- print(conMat1to2::OUT)
+      -- print(conMat2to1::OUT)
+      -- print("conversion matrices initialized"::OUT)
+      --we finish the function for one case, hence reset initialization flag
+      init? := false
+      void()$Void
+      
+ 
+    coerce(x:F1) ==
+      inGroundField?(x)$F1 => retract(x)$F1 :: F2
+      -- if x is already in GF then we can use a simple coercion
+      defPol1 =$(SUP GF) defPol2 => convertWRTsameDefPol12(x)
+      convertWRTdifferentDefPol12(x)
+ 
+    convertWRTsameDefPol12(x:F1)  ==
+      repType1 = repType2 => x pretend F2
+      -- same groundfields, same defining polynomials, same
+      -- representation types --> F1 = F2, x is already in F2
+      repType1 = "cyclic" =>
+        x = 0$F1 => 0$F2
+      -- the SI corresponding to the cyclic representation is the exponent of
+      -- the primitiveElement, therefore we exponentiate the primitiveElement
+      -- of F2 by it.
+        primitiveElement()$F2 **$F2 (x pretend SI)
+      repType2 = "cyclic" =>
+        x = 0$F1 => 0$F2
+      -- to get the exponent, we have to take the discrete logarithm of the
+      -- element in the given field.
+        (discreteLog(x)$F1 pretend SI) pretend F2
+      -- here one of the representation types is "normal"
+      if init? then initialize()
+      -- here a conversion matrix is necessary, (see initialize())
+      represents(conMat1to2 *$(Matrix GF) coordinates(x)$F1)$F2
+ 
+    convertWRTdifferentDefPol12(x:F1) ==
+      if init? then initialize()
+      -- if we want to convert into a 'smaller' field, we have to test,
+      -- whether the element is in the subfield of the 'bigger' field, which
+      -- corresponds to the 'smaller' field
+      if degree1 > degree2 then
+        if positiveRemainder(degree2,degree(x)$F1)^= 0 then
+          error "coerce: element doesn't belong to smaller field"
+      represents(conMat1to2 *$(Matrix GF) coordinates(x)$F1)$F2
+ 
+-- the three functions below equal the three functions above up to
+-- '1' exchanged by '2' in all domain and variable names
+ 
+ 
+    coerce(x:F2) ==
+      inGroundField?(x)$F2 => retract(x)$F2 :: F1
+      -- if x is already in GF then we can use a simple coercion
+      defPol1 =$(SUP GF) defPol2 => convertWRTsameDefPol21(x)
+      convertWRTdifferentDefPol21(x)
+ 
+    convertWRTsameDefPol21(x:F2)  ==
+      repType1 = repType2 => x pretend F1
+      -- same groundfields, same defining polynomials,
+      -- same representation types --> F1 = F2, that is:
+      -- x is already in F1
+      repType2 = "cyclic" =>
+        x = 0$F2 => 0$F1
+        primitiveElement()$F1 **$F1 (x pretend SI)
+      repType1 = "cyclic" =>
+        x = 0$F2 => 0$F1
+        (discreteLog(x)$F2 pretend SI) pretend F1
+      -- here one of the representation types is "normal"
+      if init? then initialize()
+      represents(conMat2to1 *$(Matrix GF) coordinates(x)$F2)$F1
+ 
+    convertWRTdifferentDefPol21(x:F2) ==
+      if init? then initialize()
+      if degree2 > degree1 then
+        if positiveRemainder(degree1,degree(x)$F2)^= 0 then
+          error "coerce: element doesn't belong to smaller field"
+      represents(conMat2to1 *$(Matrix GF) coordinates(x)$F2)$F1
+
+@
+\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 FFHOM FiniteFieldHomomorphisms>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}