diff options
Diffstat (limited to 'src/algebra/pf.spad.pamphlet')
| -rw-r--r-- | src/algebra/pf.spad.pamphlet | 266 |
1 files changed, 266 insertions, 0 deletions
diff --git a/src/algebra/pf.spad.pamphlet b/src/algebra/pf.spad.pamphlet new file mode 100644 index 00000000..338b56c2 --- /dev/null +++ b/src/algebra/pf.spad.pamphlet @@ -0,0 +1,266 @@ +\documentclass{article} +\usepackage{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: 12 April 1991 +++ 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 + ((x pretend IntegerMod p) **$IntegerMod(p) r) pretend $ + + 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 pretend 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 + void$Void + + initializeLog() == + if initelt? then initializeElt() + -- set up tables for discrete logarithm + limit:Integer:=30 + -- the minimum size for the discrete logarithm table + for f in facOfGroupSize repeat + fac:=f.factor + base:$:=primitiveElement() ** (sizeCG quo fac) + l:Integer:=length(fac)$Integer + n:Integer:=0 + if odd?(l)$Integer then n:=shift(fac,-(l quo 2)) + else n:=shift(1,(l quo 2)) + if n < limit then + d:=(fac-1) quo limit + 1 + n:=(fac-1) quo d + 1 + tbl:TBL:=table()$TBL + a:$:=1 + for i in (0::NNI)..(n-1)::NNI repeat + insert_!([lookup(a),i::NNI]$R,tbl)$TBL + a:=a*base + insert_!([fac::PI,copy(tbl)$TBL]_ + $Record(key:PI,entry:TBL),discLogTable)$Table(PI,TBL) + -- tell user about initialization + -- print("discrete logarithm table initialized"::OUT) + -- set initialization flag + initlog? := false + void$Void + + 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 + +@ +\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} |