aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/ffnb.spad.pamphlet
diff options
context:
space:
mode:
authordos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
committerdos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
commitab8cc85adde879fb963c94d15675783f2cf4b183 (patch)
treec202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/ffnb.spad.pamphlet
downloadopen-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz
Initial population.
Diffstat (limited to 'src/algebra/ffnb.spad.pamphlet')
-rw-r--r--src/algebra/ffnb.spad.pamphlet887
1 files changed, 887 insertions, 0 deletions
diff --git a/src/algebra/ffnb.spad.pamphlet b/src/algebra/ffnb.spad.pamphlet
new file mode 100644
index 00000000..032c3501
--- /dev/null
+++ b/src/algebra/ffnb.spad.pamphlet
@@ -0,0 +1,887 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra ffnb.spad}
+\author{Johannes Grabmeier, Alfred Scheerhorn}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\begin{verbatim}
+-- 28.01.93: AS and JG: setting of initlog?, initmult?, and initelt? flags in
+-- functions initializeLog, initializeMult and initializeElt put at the
+-- end to avoid errors with interruption.
+-- factorsOfCyclicGroupSize() changed.
+-- 12.05.92: JG: long lines
+-- 25.02.92: AS: parametrization of FFNBP changed, compatible to old
+-- parametrization. Along with this some changes concerning
+-- global variables and deletion of impl. of represents.
+-- 25.02.92: AS: parameter in implementation of FFNB,FFNBX changed:
+-- Extension now generated by
+-- createLowComplexityNormalBasis(extdeg)$FFF(GF)
+-- 25.02.92: AS added following functions in FFNBP: degree,
+-- linearAssociatedExp,linearAssociatedLog,linearAssociatedOrder
+-- 19.02.92: AS: FFNBP trace + norm added.
+-- 18.02.92: AS: INBFF normalElement corrected. The old one returned a wrong
+-- result for a FFNBP(FFNBP(..)) domain.
+\end{verbatim}
+\section{package INBFF InnerNormalBasisFieldFunctions}
+<<package INBFF InnerNormalBasisFieldFunctions>>=
+)abbrev package INBFF InnerNormalBasisFieldFunctions
+++ Authors: J.Grabmeier, A.Scheerhorn
+++ Date Created: 26.03.1991
+++ Date Last Updated: 31 March 1991
+++ Basic Operations:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords: finite field, normal basis
+++ References:
+++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia of Mathematics and
+++ Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
+++ D.R.Stinson: Some observations on parallel Algorithms for fast
+++ exponentiation in GF(2^n), Siam J. Comp., Vol.19, No.4, pp.711-717,
+++ August 1990
+++ T.Itoh, S.Tsujii: A fast algorithm for computing multiplicative inverses
+++ in GF(2^m) using normal bases, Inf. and Comp. 78, pp.171-177, 1988
+++ J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
+++ AXIOM Technical Report Series, ATR/5 NP2522.
+++ Description:
+++ InnerNormalBasisFieldFunctions(GF) (unexposed):
+++ This package has functions used by
+++ every normal basis finite field extension domain.
+
+InnerNormalBasisFieldFunctions(GF): Exports == Implementation where
+ GF : FiniteFieldCategory -- the ground field
+
+ PI ==> PositiveInteger
+ NNI ==> NonNegativeInteger
+ I ==> Integer
+ SI ==> SingleInteger
+ SUP ==> SparseUnivariatePolynomial
+ VGF ==> Vector GF
+ M ==> Matrix
+ V ==> Vector
+ L ==> List
+ OUT ==> OutputForm
+ TERM ==> Record(value:GF,index:SI)
+ MM ==> ModMonic(GF,SUP GF)
+
+ Exports ==> with
+
+ setFieldInfo: (V L TERM,GF) -> Void
+ ++ setFieldInfo(m,p) initializes the field arithmetic, where m is
+ ++ the multiplication table and p is the respective normal element
+ ++ of the ground field GF.
+ random : PI -> VGF
+ ++ random(n) creates a vector over the ground field with random entries.
+ index : (PI,PI) -> VGF
+ ++ index(n,m) is a index function for vectors of length n over
+ ++ the ground field.
+ pol : VGF -> SUP GF
+ ++ pol(v) turns the vector \spad{[v0,...,vn]} into the polynomial
+ ++ \spad{v0+v1*x+ ... + vn*x**n}.
+ xn : NNI -> SUP GF
+ ++ xn(n) returns the polynomial \spad{x**n-1}.
+ dAndcExp : (VGF,NNI,SI) -> VGF
+ ++ dAndcExp(v,n,k) computes \spad{v**e} interpreting v as an element of
+ ++ normal basis field. A divide and conquer algorithm similar to the
+ ++ one from D.R.Stinson,
+ ++ "Some observations on parallel Algorithms for fast exponentiation in
+ ++ GF(2^n)", Siam J. Computation, Vol.19, No.4, pp.711-717, August 1990
+ ++ is used. Argument k is a parameter of this algorithm.
+ repSq : (VGF,NNI) -> VGF
+ ++ repSq(v,e) computes \spad{v**e} by repeated squaring,
+ ++ interpreting v as an element of a normal basis field.
+ expPot : (VGF,SI,SI) -> VGF
+ ++ expPot(v,e,d) returns the sum from \spad{i = 0} to
+ ++ \spad{e - 1} of \spad{v**(q**i*d)}, interpreting
+ ++ v as an element of a normal basis field and where q is
+ ++ the size of the ground field.
+ ++ Note: for a description of the algorithm, see T.Itoh and S.Tsujii,
+ ++ "A fast algorithm for computing multiplicative inverses in GF(2^m)
+ ++ using normal bases",
+ ++ Information and Computation 78, pp.171-177, 1988.
+ qPot : (VGF,I) -> VGF
+ ++ qPot(v,e) computes \spad{v**(q**e)}, interpreting v as an element of
+ ++ normal basis field, q the size of the ground field.
+ ++ This is done by a cyclic e-shift of the vector v.
+
+-- the semantic of the following functions is obvious from the finite field
+-- context, for description see category FAXF
+ "**" :(VGF,I) -> VGF
+ ++ x**n \undocumented{}
+ ++ See \axiomFunFrom{**}{DivisionRing}
+ "*" :(VGF,VGF) -> VGF
+ ++ x*y \undocumented{}
+ ++ See \axiomFunFrom{*}{SemiGroup}
+ "/" :(VGF,VGF) -> VGF
+ ++ x/y \undocumented{}
+ ++ See \axiomFunFrom{/}{Field}
+ norm :(VGF,PI) -> VGF
+ ++ norm(x,n) \undocumented{}
+ ++ See \axiomFunFrom{norm}{FiniteAlgebraicExtensionField}
+ trace :(VGF,PI) -> VGF
+ ++ trace(x,n) \undocumented{}
+ ++ See \axiomFunFrom{trace}{FiniteAlgebraicExtensionField}
+ inv : VGF -> VGF
+ ++ inv x \undocumented{}
+ ++ See \axiomFunFrom{inv}{DivisionRing}
+ lookup : VGF -> PI
+ ++ lookup(x) \undocumented{}
+ ++ See \axiomFunFrom{lookup}{Finite}
+ normal? : VGF -> Boolean
+ ++ normal?(x) \undocumented{}
+ ++ See \axiomFunFrom{normal?}{FiniteAlgebraicExtensionField}
+ basis : PI -> V VGF
+ ++ basis(n) \undocumented{}
+ ++ See \axiomFunFrom{basis}{FiniteAlgebraicExtensionField}
+ normalElement:PI -> VGF
+ ++ normalElement(n) \undocumented{}
+ ++ See \axiomFunFrom{normalElement}{FiniteAlgebraicExtensionField}
+ minimalPolynomial: VGF -> SUP GF
+ ++ minimalPolynomial(x) \undocumented{}
+ ++ See \axiomFunFrom{minimalPolynomial}{FiniteAlgebraicExtensionField}
+
+ Implementation ==> add
+
+-- global variables ===================================================
+
+ sizeGF:NNI:=size()$GF
+ -- the size of the ground field
+
+ multTable:V L TERM:=new(1,nil()$(L TERM))$(V L TERM)
+ -- global variable containing the multiplication table
+
+ trGen:GF:=1$GF
+ -- controls the imbedding of the ground field
+
+ logq:List SI:=[0,10::SI,16::SI,20::SI,23::SI,0,28::SI,_
+ 30::SI,32::SI,0,35::SI]
+ -- logq.i is about 10*log2(i) for the values <12 which
+ -- can match sizeGF. It's used by "**"
+
+ expTable:L L SI:=[[],_
+ [4::SI,12::SI,48::SI,160::SI,480::SI,0],_
+ [8::SI,72::SI,432::SI,0],_
+ [18::SI,216::SI,0],_
+ [32::SI,480::SI,0],[],_
+ [72::SI,0],[98::SI,0],[128::SI,0],[],[200::SI,0]]
+ -- expT is used by "**" to optimize the parameter k
+ -- before calling dAndcExp(..,..,k)
+
+-- functions ===========================================================
+
+-- computes a**(-1) = a**((q**extDeg)-2)
+-- see reference of function expPot
+ inv(a) ==
+ b:VGF:=qPot(expPot(a,(#a-1)::NNI::SI,1::SI)$$,1)$$
+ erg:VGF:=inv((a *$$ b).1 *$GF trGen)$GF *$VGF b
+
+-- "**" decides which exponentiation algorithm will be used, in order to
+-- get the fastest computation. If dAndcExp is used, it chooses the
+-- optimal parameter k for that algorithm.
+ a ** ex ==
+ e:NNI:=positiveRemainder(ex,sizeGF**((#a)::PI)-1)$I :: NNI
+ zero?(e)$NNI => new(#a,trGen)$VGF
+-- one?(e)$NNI => copy(a)$VGF
+ (e = 1)$NNI => copy(a)$VGF
+-- inGroundField?(a) => new(#a,((a.1*trGen) **$GF e))$VGF
+ e1:SI:=(length(e)$I)::SI
+ sizeGF >$I 11 =>
+ q1:SI:=(length(sizeGF)$I)::SI
+ logqe:SI:=(e1 quo$SI q1) +$SI 1$SI
+ 10::SI * (logqe + sizeGF-2) > 15::SI * e1 =>
+-- print("repeatedSquaring"::OUT)
+ repSq(a,e)
+-- print("divAndConquer(a,e,1)"::OUT)
+ dAndcExp(a,e,1)
+ logqe:SI:=((10::SI *$SI e1) quo$SI (logq.sizeGF)) +$SI 1$SI
+ k:SI:=1$SI
+ expT:List SI:=expTable.sizeGF
+ while (logqe >= expT.k) and not zero? expT.k repeat k:=k +$SI 1$SI
+ mult:I:=(sizeGF-1) *$I sizeGF **$I ((k-1)pretend NNI) +$I_
+ ((logqe +$SI k -$SI 1$SI) quo$SI k)::I -$I 2
+ (10*mult) >= (15 * (e1::I)) =>
+-- print("repeatedSquaring(a,e)"::OUT)
+ repSq(a,e)
+-- print(hconcat(["divAndConquer(a,e,"::OUT,k::OUT,")"::OUT])$OUT)
+ dAndcExp(a,e,k)
+
+-- computes a**e by repeated squaring
+ repSq(b,e) ==
+ a:=copy(b)$VGF
+-- one? e => a
+ (e = 1) => a
+ odd?(e)$I => a * repSq(a*a,(e quo 2) pretend NNI)
+ repSq(a*a,(e quo 2) pretend NNI)
+
+-- computes a**e using the divide and conquer algorithm similar to the
+-- one from D.R.Stinson,
+-- "Some observations on parallel Algorithms for fast exponentiation in
+-- GF(2^n)", Siam J. Computation, Vol.19, No.4, pp.711-717, August 1990
+ dAndcExp(a,e,k) ==
+ plist:List VGF:=[copy(a)$VGF]
+ qk:I:=sizeGF**(k pretend NNI)
+ for j in 2..(qk-1) repeat
+ if positiveRemainder(j,sizeGF)=0 then b:=qPot(plist.(j quo sizeGF),1)$$
+ else b:=a *$$ last(plist)$(List VGF)
+ plist:=concat(plist,b)
+ l:List NNI:=nil()
+ ex:I:=e
+ while not(ex = 0) repeat
+ l:=concat(l,positiveRemainder(ex,qk) pretend NNI)
+ ex:=ex quo qk
+ if first(l)=0 then erg:VGF:=new(#a,trGen)$VGF
+ else erg:VGF:=plist.(first(l))
+ i:SI:=k
+ for j in rest(l) repeat
+ if j^=0 then erg:=erg *$$ qPot(plist.j,i)$$
+ i:=i+k
+ erg
+
+ a * b ==
+ e:SI:=(#a)::SI
+ erg:=zero(#a)$VGF
+ for t in multTable.1 repeat
+ for j in 1..e repeat
+ y:=t.value -- didn't work without defining x and y
+ x:=t.index
+ k:SI:=addmod(x,j::SI,e)$SI +$SI 1$SI
+ erg.k:=erg.k +$GF a.j *$GF b.j *$GF y
+ for i in 1..e-1 repeat
+ for j in i+1..e repeat
+ for t in multTable.(j-i+1) repeat
+ y:=t.value -- didn't work without defining x and y
+ x:=t.index
+ k:SI:=addmod(x,i::SI,e)$SI +$SI 1$SI
+ erg.k:GF:=erg.k +$GF (a.i *$GF b.j +$GF a.j *$GF b.i) *$GF y
+ erg
+
+ lookup(x) ==
+ erg:I:=0
+ for j in (#x)..1 by -1 repeat
+ erg:=(erg * sizeGF) + (lookup(x.j)$GF rem sizeGF)
+ erg=0 => (sizeGF**(#x)) :: PI
+ erg :: PI
+
+-- computes the norm of a over GF**d, d must devide extdeg
+-- see reference of function expPot below
+ norm(a,d) ==
+ dSI:=d::SI
+ r:=divide((#a)::SI,dSI)
+ not(r.remainder = 0) => error "norm: 2.arg must divide extdeg"
+ expPot(a,r.quotient,dSI)$$
+
+-- computes expPot(a,e,d) = sum form i=0 to e-1 over a**(q**id))
+-- see T.Itoh and S.Tsujii,
+-- "A fast algorithm for computing multiplicative inverses in GF(2^m)
+-- using normal bases",
+-- Information and Computation 78, pp.171-177, 1988
+ expPot(a,e,d) ==
+ deg:SI:=(#a)::SI
+ e=1 => copy(a)$VGF
+ k2:SI:=d
+ y:=copy(a)
+ if bit?(e,0) then
+ erg:=copy(y)
+ qpot:SI:=k2
+ else
+ erg:=new(#a,inv(trGen)$GF)$VGF
+ qpot:SI:=0
+ for k in 1..length(e) repeat
+ y:= y *$$ qPot(y,k2)
+ k2:=addmod(k2,k2,deg)$SI
+ if bit?(e,k) then
+ erg:=erg *$$ qPot(y,qpot)
+ qpot:=addmod(qpot,k2,deg)$SI
+ erg
+
+-- computes qPot(a,n) = a**(q**n), q=size of GF
+ qPot(e,n) ==
+ ei:=(#e)::SI
+ m:SI:= positiveRemainder(n::SI,ei)$SI
+ zero?(m) => e
+ e1:=zero(#e)$VGF
+ for i in m+1..ei repeat e1.i:=e.(i-m)
+ for i in 1..m repeat e1.i:=e.(ei+i-m)
+ e1
+
+ trace(a,d) ==
+ dSI:=d::SI
+ r:=divide((#a)::SI,dSI)$SI
+ not(r.remainder = 0) => error "trace: 2.arg must divide extdeg"
+ v:=copy(a.(1..dSI))$VGF
+ sSI:SI:=r.quotient
+ for i in 1..dSI repeat
+ for j in 1..sSI-1 repeat
+ v.i:=v.i+a.(i+j::SI*dSI)
+ v
+
+ random(n) ==
+ v:=zero(n)$VGF
+ for i in 1..n repeat v.i:=random()$GF
+ v
+
+
+ xn(m) == monomial(1,m)$(SUP GF) - 1$(SUP GF)
+
+ normal?(x) ==
+ gcd(xn(#x),pol(x))$(SUP GF) = 1 => true
+ false
+
+ x:VGF / y:VGF == x *$$ inv(y)$$
+
+
+ setFieldInfo(m,n) ==
+ multTable:=m
+ trGen:=n
+ void()$Void
+
+ minimalPolynomial(x) ==
+ dx:=#x
+ y:=new(#x,inv(trGen)$GF)$VGF
+ m:=zero(dx,dx+1)$(M GF)
+ for i in 1..dx+1 repeat
+ dy:=#y
+ for j in 1..dy repeat
+ for k in 0..((dx quo dy)-1) repeat
+ qsetelt_!(m,j+k*dy,i,y.j)$(M GF)
+ y:=y *$$ x
+ v:=first nullSpace(m)$(M GF)
+ pol(v)$$
+
+ basis(n) ==
+ bas:(V VGF):=new(n,zero(n)$VGF)$(V VGF)
+ for i in 1..n repeat
+ uniti:=zero(n)$VGF
+ qsetelt_!(uniti,i,1$GF)$VGF
+ qsetelt_!(bas,i,uniti)$(V VGF)
+ bas
+
+ normalElement(n) ==
+ v:=zero(n)$VGF
+ qsetelt_!(v,1,1$GF)
+ v
+-- normalElement(n) == index(n,1)$$
+
+ index(degm,n) ==
+ m:I:=n rem$I (sizeGF ** degm)
+ erg:=zero(degm)$VGF
+ for j in 1..degm repeat
+ erg.j:=index((sizeGF+(m rem sizeGF)) pretend PI)$GF
+ m:=m quo sizeGF
+ erg
+
+ pol(x) ==
+ +/[monomial(x.i,(i-1)::NNI)$(SUP GF) for i in 1..(#x)::I]
+
+@
+\section{domain FFNBP FiniteFieldNormalBasisExtensionByPolynomial}
+<<domain FFNBP FiniteFieldNormalBasisExtensionByPolynomial>>=
+)abbrev domain FFNBP FiniteFieldNormalBasisExtensionByPolynomial
+++ Authors: J.Grabmeier, A.Scheerhorn
+++ Date Created: 26.03.1991
+++ Date Last Updated: 08 May 1991
+++ Basic Operations:
+++ Related Constructors: InnerNormalBasisFieldFunctions, FiniteFieldFunctions,
+++ Also See: FiniteFieldExtensionByPolynomial,
+++ FiniteFieldCyclicGroupExtensionByPolynomial
+++ AMS Classifications:
+++ Keywords: finite field, normal basis
+++ References:
+++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia 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:
+++ FiniteFieldNormalBasisExtensionByPolynomial(GF,uni) implements a
+++ finite extension of the ground field {\em GF}. The elements are
+++ represented by coordinate vectors with respect to. a normal basis,
+++ i.e. a basis
+++ consisting of the conjugates (q-powers) of an element, in this case
+++ called normal element, where q is the size of {\em GF}.
+++ The normal element is chosen as a root of the extension
+++ polynomial, which MUST be normal over {\em GF} (user responsibility)
+FiniteFieldNormalBasisExtensionByPolynomial(GF,uni): Exports == _
+ Implementation where
+ GF : FiniteFieldCategory -- the ground field
+ uni : Union(SparseUnivariatePolynomial GF,_
+ Vector List Record(value:GF,index:SingleInteger))
+
+ PI ==> PositiveInteger
+ NNI ==> NonNegativeInteger
+ I ==> Integer
+ SI ==> SingleInteger
+ SUP ==> SparseUnivariatePolynomial
+ V ==> Vector GF
+ M ==> Matrix GF
+ OUT ==> OutputForm
+ TERM ==> Record(value:GF,index:SI)
+ R ==> Record(key:PI,entry:NNI)
+ TBL ==> Table(PI,NNI)
+ FFF ==> FiniteFieldFunctions(GF)
+ INBFF ==> InnerNormalBasisFieldFunctions(GF)
+
+ Exports ==> FiniteAlgebraicExtensionField(GF) with
+
+ getMultiplicationTable: () -> Vector List TERM
+ ++ getMultiplicationTable() returns the multiplication
+ ++ table for the normal basis of the field.
+ ++ This table is used to perform multiplications between field elements.
+ getMultiplicationMatrix:() -> M
+ ++ getMultiplicationMatrix() returns the multiplication table in
+ ++ form of a matrix.
+ sizeMultiplication:() -> NNI
+ ++ sizeMultiplication() returns the number of entries in the
+ ++ multiplication table of the field.
+ ++ Note: the time of multiplication
+ ++ of field elements depends on this size.
+ Implementation ==> add
+
+-- global variables ===================================================
+
+ Rep:= V -- elements are represented by vectors over GF
+
+ alpha :=new()$Symbol :: OutputForm
+ -- get a new Symbol for the output representation of the elements
+
+ initlog?:Boolean:=true
+ -- gets false after initialization of the logarithm table
+
+ initelt?:Boolean:=true
+ -- gets false after initialization of the primitive element
+
+ initmult?:Boolean:=true
+ -- gets false after initialization of the multiplication
+ -- table or the primitive element
+
+ extdeg:PI :=1
+
+ defpol:SUP(GF):=0$SUP(GF)
+ -- the defining polynomial
+
+ multTable:Vector List TERM:=new(1,nil()$(List TERM))
+ -- global variable containing the multiplication table
+
+ if uni case (Vector List TERM) then
+ multTable:=uni :: (Vector List TERM)
+ extdeg:= (#multTable) pretend PI
+ vv:V:=new(extdeg,0)$V
+ vv.1:=1$GF
+ setFieldInfo(multTable,1$GF)$INBFF
+ defpol:=minimalPolynomial(vv)$INBFF
+ initmult?:=false
+ else
+ defpol:=uni :: SUP(GF)
+ extdeg:=degree(defpol)$(SUP GF) pretend PI
+ multTable:Vector List TERM:=new(extdeg,nil()$(List TERM))
+
+ basisOutput : List OUT :=
+ qs:OUT:=(q::Symbol)::OUT
+ append([alpha, alpha **$OUT qs],_
+ [alpha **$OUT (qs **$OUT i::OUT) for i in 2..extdeg-1] )
+
+
+ facOfGroupSize :=nil()$(List Record(factor:Integer,exponent:Integer))
+ -- the factorization of the cyclic group size
+
+
+ traceAlpha:GF:=-$GF coefficient(defpol,(degree(defpol)-1)::NNI)
+ -- the inverse of the trace of the normalElt
+ -- is computed here. It defines the imbedding of
+ -- GF in the extension field
+
+ primitiveElt:PI:=1
+ -- for the lookup the primitive Element computed by createPrimitiveElement()
+
+ 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 ===========================================================
+
+ initializeLog: () -> Void
+ initializeElt: () -> Void
+ initializeMult: () -> Void
+
+
+ coerce(v:GF):$ == new(extdeg,v /$GF traceAlpha)$Rep
+ represents(v) == v::$
+
+ degree(a) ==
+ d:PI:=1
+ b:= qPot(a::Rep,1)$INBFF
+ while (b^=a) repeat
+ b:= qPot(b::Rep,1)$INBFF
+ d:=d+1
+ d
+
+ linearAssociatedExp(x,f) ==
+ xm:SUP(GF):=monomial(1$GF,extdeg)$(SUP GF) - 1$(SUP GF)
+ r:= (f * pol(x::Rep)$INBFF) rem xm
+ vectorise(r,extdeg)$(SUP GF)
+ linearAssociatedLog(x) == pol(x::Rep)$INBFF
+ linearAssociatedOrder(x) ==
+ xm:SUP(GF):=monomial(1$GF,extdeg)$(SUP GF) - 1$(SUP GF)
+ xm quo gcd(xm,pol(x::Rep)$INBFF)
+ linearAssociatedLog(b,x) ==
+ zero? x => 0
+ xm:SUP(GF):=monomial(1$GF,extdeg)$(SUP GF) - 1$(SUP GF)
+ e:= extendedEuclidean(pol(b::Rep)$INBFF,xm,pol(x::Rep)$INBFF)$(SUP GF)
+ e = "failed" => "failed"
+ e1:= e :: Record(coef1:(SUP GF),coef2:(SUP GF))
+ e1.coef1
+
+ getMultiplicationTable() ==
+ if initmult? then initializeMult()
+ multTable
+ getMultiplicationMatrix() ==
+ if initmult? then initializeMult()
+ createMultiplicationMatrix(multTable)$FFF
+ sizeMultiplication() ==
+ if initmult? then initializeMult()
+ sizeMultiplication(multTable)$FFF
+
+ trace(a:$) == retract trace(a,1)
+ norm(a:$) == retract norm(a,1)
+ generator() == normalElement(extdeg)$INBFF
+ basis(n:PI) ==
+ (extdeg rem n) ^= 0 => error "argument must divide extension degree"
+ [Frobenius(trace(normalElement,n),i) for i in 0..(n-1)]::(Vector $)
+
+ a:GF * x:$ == a *$Rep x
+
+ x:$/a:GF == x/coerce(a)
+-- x:$ / a:GF ==
+-- a = 0$GF => error "division by zero"
+-- x * inv(coerce(a))
+
+
+ coordinates(x:$) == x::Rep
+
+ Frobenius(e) == qPot(e::Rep,1)$INBFF
+ Frobenius(e,n) == qPot(e::Rep,n)$INBFF
+
+ retractIfCan(x) ==
+ inGroundField?(x) =>
+ x.1 *$GF traceAlpha
+ "failed"
+
+ retract(x) ==
+ inGroundField?(x) =>
+ x.1 *$GF traceAlpha
+ error("element not in ground field")
+
+-- to get a "normal basis like" output form
+ coerce(x:$):OUT ==
+ l:List OUT:=nil()$(List OUT)
+ n : PI := extdeg
+-- one? n => (x.1) :: OUT
+ (n = 1) => (x.1) :: OUT
+ for i in 1..n for b in basisOutput repeat
+ if not zero? x.i then
+ mon : OUT :=
+-- one? x.i => b
+ (x.i = 1) => b
+ ((x.i)::OUT) *$OUT b
+ l:=cons(mon,l)$(List OUT)
+ null(l)$(List OUT) => (0::OUT)
+ r:=reduce("+",l)$(List OUT)
+ r
+
+ initializeElt() ==
+ facOfGroupSize := factors factor(size()$GF**extdeg-1)$I
+ -- get a primitive element
+ primitiveElt:=lookup(createPrimitiveElement())
+ initelt?:=false
+ void()$Void
+
+ initializeMult() ==
+ multTable:=createMultiplicationTable(defpol)$FFF
+ setFieldInfo(multTable,traceAlpha)$INBFF
+ -- reset initialize flag
+ initmult?:=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:$:=index(primitiveElt)**((size()$GF**extdeg -$I 1$I) quo$I fac)
+ l:Integer:=length(fac)$Integer
+ n:Integer:=0
+ if odd?(l)$I then n:=shift(fac,-$I (l quo$I 2))$I
+ else n:=shift(1,l quo$I 2)$I
+ if n <$I limit then
+ d:=(fac -$I 1$I) quo$I limit +$I 1$I
+ n:=(fac -$I 1$I) quo$I d +$I 1$I
+ 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)
+ initlog?:=false
+ -- tell user about initialization
+ --print("discrete logarithm table initialized"::OUT)
+ void()$Void
+
+ 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)
+
+ factorsOfCyclicGroupSize() ==
+ if empty? facOfGroupSize then initializeElt()
+ facOfGroupSize
+
+ extensionDegree() == extdeg
+
+ sizeOfGroundField() == size()$GF pretend NNI
+
+ definingPolynomial() == defpol
+
+ trace(a,d) ==
+ v:=trace(a::Rep,d)$INBFF
+ erg:=v
+ for i in 2..(extdeg quo d) repeat
+ erg:=concat(erg,v)$Rep
+ erg
+
+ characteristic() == characteristic()$GF
+
+ random() == random(extdeg)$INBFF
+
+ x:$ * y:$ ==
+ if initmult? then initializeMult()
+ setFieldInfo(multTable,traceAlpha)$INBFF
+ x::Rep *$INBFF y::Rep
+
+
+ 1 == new(extdeg,inv(traceAlpha)$GF)$Rep
+
+ 0 == zero(extdeg)$Rep
+
+ size() == size()$GF ** extdeg
+
+ index(n:PI) == index(extdeg,n)$INBFF
+
+ lookup(x:$) == lookup(x::Rep)$INBFF
+
+
+ basis() ==
+ a:=basis(extdeg)$INBFF
+ vector([e::$ for e in entries a])
+
+
+ x:$ ** e:I ==
+ if initmult? then initializeMult()
+ setFieldInfo(multTable,traceAlpha)$INBFF
+ (x::Rep) **$INBFF e
+
+ normal?(x) == normal?(x::Rep)$INBFF
+
+ -(x:$) == -$Rep x
+ x:$ + y:$ == x +$Rep y
+ x:$ - y:$ == x -$Rep y
+ x:$ = y:$ == x =$Rep y
+ n:I * x:$ == x *$Rep (n::GF)
+
+
+
+
+ representationType() == "normal"
+
+ minimalPolynomial(a) ==
+ if initmult? then initializeMult()
+ setFieldInfo(multTable,traceAlpha)$INBFF
+ minimalPolynomial(a::Rep)$INBFF
+
+-- is x an element of the ground field GF ?
+ inGroundField?(x) ==
+ erg:=true
+ for i in 2..extdeg repeat
+ not(x.i =$GF x.1) => erg:=false
+ erg
+
+ x:$ / y:$ ==
+ if initmult? then initializeMult()
+ setFieldInfo(multTable,traceAlpha)$INBFF
+ x::Rep /$INBFF y::Rep
+
+ inv(a) ==
+ if initmult? then initializeMult()
+ setFieldInfo(multTable,traceAlpha)$INBFF
+ inv(a::Rep)$INBFF
+
+ norm(a,d) ==
+ if initmult? then initializeMult()
+ setFieldInfo(multTable,traceAlpha)$INBFF
+ norm(a::Rep,d)$INBFF
+
+ normalElement() == normalElement(extdeg)$INBFF
+
+@
+\section{domain FFNBX FiniteFieldNormalBasisExtension}
+<<domain FFNBX FiniteFieldNormalBasisExtension>>=
+)abbrev domain FFNBX FiniteFieldNormalBasisExtension
+++ Authors: J.Grabmeier, A.Scheerhorn
+++ Date Created: 26.03.1991
+++ Date Last Updated:
+++ Basic Operations:
+++ Related Constructors: FiniteFieldNormalBasisExtensionByPolynomial,
+++ FiniteFieldPolynomialPackage
+++ Also See: FiniteFieldExtension, FiniteFieldCyclicGroupExtension
+++ AMS Classifications:
+++ Keywords: finite field, normal basis
+++ References:
+++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia 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:
+++ FiniteFieldNormalBasisExtensionByPolynomial(GF,n) implements a
+++ finite extension field of degree n over the ground field {\em GF}.
+++ The elements are represented by coordinate vectors with respect
+++ to a normal basis,
+++ i.e. a basis consisting of the conjugates (q-powers) of an element, in
+++ this case called normal element. This is chosen as a root of the extension
+++ polynomial, created by {\em createNormalPoly} from
+++ \spadtype{FiniteFieldPolynomialPackage}
+FiniteFieldNormalBasisExtension(GF,extdeg):_
+ Exports == Implementation where
+ GF : FiniteFieldCategory -- the ground field
+ extdeg: PositiveInteger -- the extension degree
+ NNI ==> NonNegativeInteger
+ FFF ==> FiniteFieldFunctions(GF)
+ TERM ==> Record(value:GF,index:SingleInteger)
+ Exports ==> FiniteAlgebraicExtensionField(GF) with
+ getMultiplicationTable: () -> Vector List TERM
+ ++ getMultiplicationTable() returns the multiplication
+ ++ table for the normal basis of the field.
+ ++ This table is used to perform multiplications between field elements.
+ getMultiplicationMatrix: () -> Matrix GF
+ ++ getMultiplicationMatrix() returns the multiplication table in
+ ++ form of a matrix.
+ sizeMultiplication:() -> NNI
+ ++ sizeMultiplication() returns the number of entries in the
+ ++ multiplication table of the field. Note: the time of multiplication
+ ++ of field elements depends on this size.
+
+ Implementation ==> FiniteFieldNormalBasisExtensionByPolynomial(GF,_
+ createLowComplexityNormalBasis(extdeg)$FFF)
+
+@
+\section{domain FFNB FiniteFieldNormalBasis}
+<<domain FFNB FiniteFieldNormalBasis>>=
+)abbrev domain FFNB FiniteFieldNormalBasis
+++ Authors: J.Grabmeier, A.Scheerhorn
+++ Date Created: 26.03.1991
+++ Date Last Updated:
+++ Basic Operations:
+++ Related Constructors: FiniteFieldNormalBasisExtensionByPolynomial,
+++ FiniteFieldPolynomialPackage
+++ Also See: FiniteField, FiniteFieldCyclicGroup
+++ AMS Classifications:
+++ Keywords: finite field, normal basis
+++ References:
+++ R.Lidl, H.Niederreiter: Finite Field, Encyclopedia 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:
+++ FiniteFieldNormalBasis(p,n) implements a
+++ finite extension field of degree n over the prime field with p elements.
+++ The elements are represented by coordinate vectors with respect to
+++ a normal basis,
+++ i.e. a basis consisting of the conjugates (q-powers) of an element, in
+++ this case called normal element.
+++ This is chosen as a root of the extension polynomial
+++ created by \spadfunFrom{createNormalPoly}{FiniteFieldPolynomialPackage}.
+FiniteFieldNormalBasis(p,extdeg):_
+ Exports == Implementation where
+ p : PositiveInteger
+ extdeg: PositiveInteger -- the extension degree
+ NNI ==> NonNegativeInteger
+ FFF ==> FiniteFieldFunctions(PrimeField(p))
+ TERM ==> Record(value:PrimeField(p),index:SingleInteger)
+ Exports ==> FiniteAlgebraicExtensionField(PrimeField(p)) with
+ getMultiplicationTable: () -> Vector List TERM
+ ++ getMultiplicationTable() returns the multiplication
+ ++ table for the normal basis of the field.
+ ++ This table is used to perform multiplications between field elements.
+ getMultiplicationMatrix: () -> Matrix PrimeField(p)
+ ++ getMultiplicationMatrix() returns the multiplication table in
+ ++ form of a matrix.
+ sizeMultiplication:() -> NNI
+ ++ sizeMultiplication() returns the number of entries in the
+ ++ multiplication table of the field. Note: The time of multiplication
+ ++ of field elements depends on this size.
+
+ Implementation ==> FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(p),_
+ createLowComplexityNormalBasis(extdeg)$FFF)
+
+@
+\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 INBFF InnerNormalBasisFieldFunctions>>
+<<domain FFNBP FiniteFieldNormalBasisExtensionByPolynomial>>
+<<domain FFNBX FiniteFieldNormalBasisExtension>>
+<<domain FFNB FiniteFieldNormalBasis>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}