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

\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra pf.spad}
\author{N.N., Johannes Grabmeier, Alfred Scheerhorn}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{domain IPF InnerPrimeField}
<<domain IPF InnerPrimeField>>=
)abbrev domain IPF InnerPrimeField
-- Argument MUST be a prime.
-- This domain does not check, PrimeField does.
++ Authors: N.N., J.Grabmeier, A.Scheerhorn
++ Date Created: ?, November 1990, 26.03.1991
++ Date Last Updated: May 29, 2009
++ Basic Operations:
++ Related Constructors: PrimeField
++ Also See:
++ AMS Classifications:
++ Keywords: prime characteristic, prime field, finite field
++ References:
++  R.Lidl, H.Niederreiter: Finite Field, Encycoldia of Mathematics and
++  Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
++  AXIOM Technical Report Series, to appear.
++ Description:
++   InnerPrimeField(p) implements the field with p elements.
++   Note: argument p MUST be a prime (this domain does not check).
++   See \spadtype{PrimeField} for a domain that does check.


InnerPrimeField(p:PositiveInteger): Exports == Implementation where

  I   ==> Integer
  NNI ==> NonNegativeInteger
  PI  ==> PositiveInteger
  TBL ==> Table(PI,NNI)
  R   ==> Record(key:PI,entry:NNI)
  SUP ==> SparseUnivariatePolynomial
  OUT ==> OutputForm

  Exports ==> Join(FiniteFieldCategory,FiniteAlgebraicExtensionField($),_
                ConvertibleTo(Integer))

  Implementation ==> IntegerMod p add

    initializeElt:() -> Void
    initializeLog:() -> Void

-- global variables ====================================================

    primitiveElt:PI:=1
    -- for the lookup the primitive Element computed by createPrimitiveElement()

    sizeCG  :=(p-1) pretend NonNegativeInteger
    -- the size of the cyclic group

    facOfGroupSize := nil()$(List Record(factor:Integer,exponent:Integer))
    -- the factorization of the cyclic group size

    initlog?:Boolean:=true
    -- gets false after initialization of the logarithm table

    initelt?:Boolean:=true
    -- gets false after initialization of the primitive Element


    discLogTable:Table(PI,TBL):=table()$Table(PI,TBL)
    -- tables indexed by the factors of the size q of the cyclic group
    -- discLogTable.factor is a table of with keys
    -- primitiveElement() ** (i * (q 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 ===========================================================

    generator() == 1

    -- This uses x**(p-1)=1 (mod p), so x**(q(p-1)+r) = x**r (mod p)
    x:$ ** n:Integer ==
      zero?(n) => 1
      zero?(x) => 0
      r := positiveRemainder(n,p-1)::NNI
      per (rep(x) **$IntegerMod(p) r)

    if p <= convert(max()$SingleInteger)@Integer then
      q := p::SingleInteger

      recip x ==
        zero?(y := convert(x)@Integer :: SingleInteger) => "failed"
        invmod(y, q)::Integer::$
    else
      recip x ==
        zero?(y := convert(x)@Integer) => "failed"
        invmod(y, p)::$

    convert(x:$) == x pretend I

    normalElement() == 1

    createNormalElement() == 1

    characteristic == p

    factorsOfCyclicGroupSize() ==
      p=2 => facOfGroupSize -- this fixes an infinite loop of functions
                            -- calls, problem was that factors factor(1)
                            -- is the empty list
      if empty? facOfGroupSize then initializeElt()
      facOfGroupSize

    representationType() == "prime"

    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 :: TBL

    primitiveElement() ==
      if initelt? then initializeElt()
      index(primitiveElt)

    initializeElt() ==
      facOfGroupSize:=factors(factor(sizeCG)$I)$(Factored I)
      -- get a primitive element
      primitiveElt:=lookup(createPrimitiveElement())
      -- set initialization flag
      initelt? := false

    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)
      -- tell user about initialization
      --    print("discrete logarithm table initialized"::OUT)
      -- set initialization flag
      initlog? := false

    degree(x):PI == 1::PositiveInteger
    extensionDegree():PI == 1::PositiveInteger

--    sizeOfGroundField() == p::NonNegativeInteger

    inGroundField?(x)  == true

    coordinates(x: %) == new(1,x)$(Vector $)

    represents(v)  == v.1

    retract(x) == x

    retractIfCan(x) == x

    basis() == new(1,1::$)$(Vector $)
    basis(n:PI) ==
      n = 1 => basis()
      error("basis: argument must divide extension degree")

    definingPolynomial() ==
      monomial(1,1)$(SUP $) - monomial(1,0)$(SUP $)


    minimalPolynomial(x) ==
      monomial(1,1)$(SUP $) - monomial(x,0)$(SUP $)

    charthRoot(x: %): % == x

    before?(x,y) == before?(convert x, convert y)$I
@
\section{domain PF PrimeField}
<<domain PF PrimeField>>=
)abbrev domain PF PrimeField
++ Authors: N.N.,
++ Date Created: November 1990, 26.03.1991
++ Date Last Updated: 31 March 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: prime characteristic, prime field, finite field
++ References:
++  R.Lidl, H.Niederreiter: Finite Field, Encycoldia of Mathematics and
++  Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
++ Description:
++   PrimeField(p) implements the field with p elements if p is a
++   prime number.
++   Error: if p is not prime.
++   Note: this domain does not check that argument is a prime.
--++   with new compiler, want to put the error check before the add
PrimeField(p:PositiveInteger): Exp == Impl where
  Exp ==> Join(FiniteFieldCategory,FiniteAlgebraicExtensionField($),_
    ConvertibleTo(Integer))
  Impl ==>  InnerPrimeField(p) add
    if not prime?(p)$IntegerPrimesPackage(Integer) then
      error "Argument to prime field must be a prime"

@
\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 IPF InnerPrimeField>>
<<domain PF PrimeField>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}