\documentclass{article} \usepackage{open-axiom} \begin{document} \title{\$SPAD/src/algebra ffp.spad} \author{Johannes Grabmeier, Alfred Scheerhorn, Robert Sutor, Oswald Gschnitzer} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \begin{verbatim} -- 28.01.93: AS and JG: setting of initlog? and initelt? flags in -- functions initializeLog and initializeElt put at the -- end to avoid errors with interruption. createNormalElement() -- included in function initializeElt. Function createNormalElement() set -- into comments. factorsOfCyclicGroupSize() changed. -- 12.05.92: JG: long lines -- 18.02.92: AS: degree: $ -> PI added, faster then category version -- 18.06.91: AS: createNormalElement added: -- the version in ffcat.spad needs too long -- for finding a normal element, because of the "correlation" between -- the "additive" structure of the index function and the additive -- structure of the field. Our experiments show that this version is -- much faster. -- 05.04.91 JG: comments, IFF -- 04.04.91 JG: error message in function tablesOfDiscreteLogarithm changed -- 04.04.91 JG: comment of FFP was changed \end{verbatim} \section{domain FFP FiniteFieldExtensionByPolynomial} <>= )abbrev domain FFP FiniteFieldExtensionByPolynomial ++ Authors: R.Sutor, J. Grabmeier, O. Gschnitzer, A. Scheerhorn ++ Date Created: ++ Date Last Updated: May 29, 2009 ++ Basic Operations: ++ Related Constructors: ++ Also See: FiniteFieldCyclicGroupExtensionByPolynomial, ++ FiniteFieldNormalBasisExtensionByPolynomial ++ AMS Classifications: ++ Keywords: field, extension field, algebraic extension, ++ finite extension, finite field, Galois field ++ Reference: ++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an ++ 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: ++ FiniteFieldExtensionByPolynomial(GF, defpol) implements the extension ++ of the finite field {\em GF} generated by the extension polynomial ++ {\em defpol} which MUST be irreducible. ++ Note: the user has the responsibility to ensure that ++ {\em defpol} is irreducible. FiniteFieldExtensionByPolynomial(GF:FiniteFieldCategory,_ defpol:SparseUnivariatePolynomial GF): Exports == Implementation where -- GF : FiniteFieldCategory -- defpol : SparseUnivariatePolynomial GF PI ==> PositiveInteger NNI ==> NonNegativeInteger SUP ==> SparseUnivariatePolynomial I ==> Integer R ==> Record(key:PI,entry:NNI) TBL ==> Table(PI,NNI) SAE ==> SimpleAlgebraicExtension(GF,SUP GF,defpol) OUT ==> OutputForm Exports ==> FiniteAlgebraicExtensionField(GF) Implementation ==> add -- global variables ==================================================== Rep:=SAE extdeg:PI := degree(defpol)$(SUP GF) pretend PI -- the extension degree alpha := new()$Symbol :: OutputForm -- a new symbol for the output form of field elements sizeCG:Integer := size()$GF**extdeg - 1 -- the order of the multiplicative group facOfGroupSize := nil()$(List Record(factor:Integer,exponent:Integer)) -- the factorization of sizeCG normalElt:PI:=1 -- for the lookup of the normal Element computed by -- createNormalElement primitiveElt:PI:=1 -- for the lookup of the primitive Element computed by -- createPrimitiveElement() initlog?:Boolean:=true -- gets false after initialization of the discrete logarithm table initelt?:Boolean:=true -- gets false after initialization of the primitive and the -- normal element discLogTable:Table(PI,TBL):=table()$Table(PI,TBL) -- tables indexed by the factors of sizeCG, -- discLogTable(factor) is a table with keys -- primitiveElement() ** (i * (sizeCG 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 =========================================================== -- createNormalElement() == -- a:=primitiveElement() -- nElt:=generator() -- for i in 1.. repeat -- normal? nElt => return nElt -- nElt:=nElt*a -- nElt generator() == reduce(monomial(1,1)$SUP(GF))$Rep norm x == resultant(defpol, lift x) initializeElt: () -> Void initializeLog: () -> Void basis(n:PI) == (extdeg rem n) ~= 0 => error "argument must divide extension degree" a:$:=norm(primitiveElement(),n) vector [a**i for i in 0..n-1] degree(x: %): PositiveInteger == y:$:=1 m:=zero(extdeg,extdeg+1)$(Matrix GF) for i in 1..extdeg+1 repeat setColumn!(m,i,coordinates(y))$(Matrix GF) y:=y*x rank(m)::PI minimalPolynomial(x:$) == y:$:=1 m:=zero(extdeg,extdeg+1)$(Matrix GF) for i in 1..extdeg+1 repeat setColumn!(m,i,coordinates(y))$(Matrix GF) y:=y*x v:=first nullSpace(m)$(Matrix GF) +/[monomial(v.(i+1),i)$(SUP GF) for i in 0..extdeg] normal?(x) == l:List List GF:=[entries coordinates x] a:=x for i in 2..extdeg repeat a:=Frobenius(a) l:=concat(l,entries coordinates a)$(List List GF) ((rank matrix(l)$(Matrix GF)) = extdeg::NNI) => true false a:GF * x:$ == a *$Rep x n:I * x:$ == n *$Rep x -x == -$Rep x random() == random()$Rep coordinates(x:$) == coordinates(x)$Rep represents(v) == represents(v)$Rep coerce(x:GF):$ == coerce(x)$Rep definingPolynomial() == defpol retract(x) == retract(x)$Rep retractIfCan(x) == retractIfCan(x)$Rep index(x) == index(x)$Rep lookup(x) == lookup(x)$Rep x:$/y:$ == x /$Rep y x:$/a:GF == x/coerce(a) -- x:$ / a:GF == -- a = 0$GF => error "division by zero" -- x * inv(coerce(a)) x:$ * y:$ == x *$Rep y x:$ + y:$ == x +$Rep y x:$ - y:$ == x -$Rep y x:$ = y:$ == x =$Rep y basis() == basis()$Rep 0 == 0$Rep 1 == 1$Rep factorsOfCyclicGroupSize() == if empty? facOfGroupSize then initializeElt() facOfGroupSize representationType() == "polynomial" 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) normalElement() == if initelt? then initializeElt() index(normalElt) initializeElt() == facOfGroupSize:=factors(factor(sizeCG)$Integer) -- get a primitive element pE:=createPrimitiveElement() primitiveElt:=lookup(pE) -- create a normal element nElt:=generator() while not normal? nElt repeat nElt:=nElt*pE normalElt:=lookup(nElt) -- set elements 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) -- set logarithm initialization flag initlog? := false -- tell user about initialization --print("discrete logarithm tables initialized"::OUT) coerce(e:$):OutputForm == outputForm(lift(e),alpha) extensionDegree(): PositiveInteger == extdeg size() == (sizeCG + 1) pretend NNI -- sizeOfGroundField() == size()$GF inGroundField?(x) == retractIfCan(x) = "failed" => false true characteristic == characteristic$GF before?(x,y) == before?(x,y)$Rep @ \section{domain FFX FiniteFieldExtension} <>= )abbrev domain FFX FiniteFieldExtension ++ Authors: R.Sutor, J. Grabmeier, A. Scheerhorn ++ Date Created: ++ Date Last Updated: 31 March 1991 ++ Basic Operations: ++ Related Constructors: FiniteFieldExtensionByPolynomial, ++ FiniteFieldPolynomialPackage ++ Also See: FiniteFieldCyclicGroupExtension, ++ FiniteFieldNormalBasisExtension ++ AMS Classifications: ++ Keywords: field, extension field, algebraic extension, ++ finite extension, finite field, Galois field ++ Reference: ++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an ++ 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: ++ FiniteFieldExtensionByPolynomial(GF, n) implements an extension ++ of the finite field {\em GF} of degree n generated by the extension ++ polynomial constructed by ++ \spadfunFrom{createIrreduciblePoly}{FiniteFieldPolynomialPackage} from ++ \spadtype{FiniteFieldPolynomialPackage}. FiniteFieldExtension(GF, n): Exports == Implementation where GF: FiniteFieldCategory n : PositiveInteger Exports ==> FiniteAlgebraicExtensionField(GF) -- MonogenicAlgebra(GF, SUP) with -- have to check this Implementation ==> FiniteFieldExtensionByPolynomial(GF, createIrreduciblePoly(n)$FiniteFieldPolynomialPackage(GF)) -- old code for generating irreducible polynomials: -- now "better" order (sparse polys first) -- generateIrredPoly(n)$IrredPolyOverFiniteField(GF)) @ \section{domain IFF InnerFiniteField} <>= )abbrev domain IFF InnerFiniteField ++ Author: ??? ++ Date Created: ??? ++ Date Last Updated: 29 May 1990 ++ Basic Operations: ++ Related Constructors: FiniteFieldExtensionByPolynomial, ++ FiniteFieldPolynomialPackage ++ Also See: FiniteFieldCyclicGroup, FiniteFieldNormalBasis ++ AMS Classifications: ++ Keywords: field, extension field, algebraic extension, ++ finite extension, finite field, Galois field ++ Reference: ++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an ++ 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: ++ InnerFiniteField(p,n) implements finite fields with \spad{p**n} elements ++ where p is assumed prime but does not check. ++ For a version which checks that p is prime, see \spadtype{FiniteField}. InnerFiniteField(p:PositiveInteger, n:PositiveInteger) == FiniteFieldExtension(InnerPrimeField p, n) @ \section{domain FF FiniteField} <>= )abbrev domain FF FiniteField ++ Author: ??? ++ Date Created: ??? ++ Date Last Updated: 29 May 1990 ++ Basic Operations: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: field, extension field, algebraic extension, ++ finite extension, finite field, Galois field ++ Reference: ++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics an ++ 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: ++ FiniteField(p,n) implements finite fields with p**n elements. ++ This packages checks that p is prime. ++ For a non-checking version, see \spadtype{InnerFiniteField}. FiniteField(p:PositiveInteger, n:PositiveInteger): _ FiniteAlgebraicExtensionField(PrimeField p) ==_ FiniteFieldExtensionByPolynomial(PrimeField p,_ createIrreduciblePoly(n)$FiniteFieldPolynomialPackage(PrimeField p)) -- old code for generating irreducible polynomials: -- now "better" order (sparse polys first) -- generateIrredPoly(n)$IrredPolyOverFiniteField(GF)) @ \section{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. @ <<*>>= <> <> <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}