\documentclass{article} \usepackage{open-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} <>= )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 -- 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 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 not zero? j 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 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} <>= import NonNegativeInteger import Matrix )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: %): PositiveInteger == 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 for i in 1..n for b in basisOutput repeat if not zero? x.i then mon : OUT := one? x.i => b ((x.i)::OUT) *$OUT b l:=cons(mon,l)$(List OUT) null(l)$(List OUT) => (0@GF::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 initializeMult() == multTable:=createMultiplicationTable(defpol)$FFF setFieldInfo(multTable,traceAlpha)$INBFF -- reset initialize flag initmult?:=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:$:=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) 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(): PositiveInteger == 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} <>= )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} <>= )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} <>= --Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. --All rights reserved. --Copyright (C) 2007-2010, Gabriel Dos Reis. --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}