(**********************************************************************) (* FinFld.ma *) (* Mathematica package of operations on finite fields *) (* 16 Mar, 2002 *) (* Robert Campbell, campbell@math.umbc.edu *) (* SCCS stuff: %Z%%P% delta=%I% edit=%G% get=%H% *) (**********************************************************************) (* Notes: We represent the finite field GF(p^n) explicitly in *) (* terms of the prime p and an irreducible degree n polynomial. *) (* An element of the field is represented as a data structure *) (* containing a representation of the field, together with a *) (* polynomial in a root of the polynomial defining the field. *) (* We allow ourselves the freedom of accepting an integer *) (* as an element of the field. Field operations are implemented *) (* by overloading the usual +,-,*,/,^ operations. *) (**********************************************************************) (* Structures: *) (* FinFld[p,n,poly,x,{facts}] *) (* The field GF(p^n) with minimum poly in var x, where *) (* facts is a list of the factors of p^n-1 *) (* ElementFinFld[poly,FinFld[]] *) (* An element of the finite field, expressed as a *) (* polynomial in the variable used to express the *) (* minimum polynomial of the field *) (**********************************************************************) (* Example: *) (* In[1]:= << FinFld.ma *) (* {CreateFinFld,ElementFinFld,FinFld,ModFinFld,PlusFinFld,...} *) (* > have been defined in package FinFld. *) (* In[2]:= gf16=CreateFinFld[x^4+x+1,x,2] *) (* Out[2]= GF(2^4) *) (* In[3]:= a = ElementFinFld[x,gf16] *) (* Out[3]= (x) *) (* GF(2^4) *) (* In[4]:= a+a *) (* Out[4]= (0) *) (* GF(2^4) *) (* In[5]:= a^15 *) (* Out[5]= (1) *) (* GF(2^4) *) (* In[6]:= a^(-1) *) (* Out[6]= (1 + x )^3 *) (* GF(2^4) *) (**********************************************************************) BeginPackage["FinFld`"] FinFld::usage="FinFld[p,n,q[x],x,stuff] represents the finite field \ of order p^n with defining polynomial q[x]."; CreateFinFld::usage="CreateFinFld[poly,var,p] or CreateFinFld[n,var,p] \ creates the necessary \ structures to represent the finite field (Galois field) of p^n \ elements, where poly is a degree n polynomial in the variable var. \ The field is represented as polynomials in a root of poly. This \ function returns a FinFld[] structure."; CharacteristicFinFld::usage="CharacteristicFinFld[FinFld[...]] returns \ the (finite integer) characteristic of the finite field."; DegreeFinFld::usage="DegreeFinFld[FinFld[...]] returns \ the (finite integer) degree of the finite field as an extension \ over the prime field."; ElementFinFld::usage="ElementFinFld[r[x],FinFld[...]] is a data \ structure which represents an element of the specified finite \ field. The FinFld structure is created with the CreateFinFld \ command."; PlusFinFld::usage="PlusFinFld[elem1,elem2] adds two elements of a \ finite field. A short form is elem1+elem2. Both parameters must have \ head ElementFinFld (one may be an Integer)."; TimesFinFld::usage="TimesFinFld[elem1,elem2] multiplies two elements of a \ finite field. A short form is elem1*elem2. Both parameters must have \ head ElementFinFld (one may be an Integer)."; InverseFinFld::usage="InverseFinFld[elem] computes the inverse of an \ element of a finite field. A short form is elem^(-1). The parameter must have \ head ElementFinFld."; PowerModFinFld::usage="PowerModFinFld[elem,n] computes elem^n, or the \ product of n copies of elem, where elem is an element of a \ finite field. A short form is elem^n. The first parameter must have \ head ElementFinFld and the second must be an integer."; ModFinFld::usage="ModFinFld[elem] forces the reduction of an element\ of a finite field, where the element is an object of type \ ElementFinFld[]."; PrimitiveFinFldQ::usage="PrimitiveFinFldQ[ElementFinFld[...]] returns \ True if the element is a primitive element in the multiplicative group."; FromListFinFld::usage="FromListFinFld[list,finfld] creates an element \ of the finite field defined by the second parameter. The element created \ is represented as a polynomial whose coefficients are given by the list, \ with low order coefficient first." ToListFinFld::usage="ToListFinFld[elt] converts the finite field element \ to a list of its coefficients, low order term first." FromIntegerFinFld::usage="FromIntegerFinFld[n,finfld] creates an element \ of the finite field defined by the second parameter."; ToIntegerFinFld::usage="ToIntegerFinFld[elt] converts the finite field \ element to an integer."; TraceFinFld::usage="TraceFinFld[elt] computes the trace of the finite \ field element. Currently the trace is computed over the base prime \ field, although more general traces may be computed in future."; ListFinFld::usage="ListFinFld[finfld] generates a list of the elements \ of the specified finite field."; MinPolyFinFld::usage="MinPolyFinFld[elt,var] computes the minimal \ polynomial of the finite field element and expresses it as a \ polynomial in var. Currently this is computed over the base prime \ field, although computations over intermediate extensions may be \ computed in future."; VerifyIrred::usage="VerifyIrred is an option for the CreateFinFld[] \ function, taking the values True or False. If this is set to True \ the polynomial defining the field is checked for irreducibility."; FactorOrder::usage="FactorOrder is an option for the CreateFinFld[] \ function, taking the values True or False. If this is set to True \ the order of the multiplicative group, p^n-1, is factored and \ saved with the field definition."; (**********************************************************************) Begin["`Private`"] Format[FinFld[p_,n_,___]] := SequenceForm["GF(",p,"^",n,")"]; Format[ElementFinFld[expr_,ff_FinFld,___]] := \ SequenceForm["(",expr,")",Subscript[ff]]; Options[CreateFinFld] = {VerifyIrred -> True, FactorOrder->False}; General::notimplemented="The Finite Field function `` is not currently \ implemented. Better luck next time."; CreateFinFld::notprime="The characteristic of the finite field, ``, is not prime."; CreateFinFld::notpoly="The defining polynomial of the finite field must be a \ polynomila in a single variable with integer coefficients."; CreateFinFld::notirredpoly="The defining polynomial for the finite field, \ `1`, is not irreducible modulo `2`."; CreateFinFld[n_Integer,var_Symbol,p_Integer,options___] := \ CreateFinFld[FindIrred[n,p,var],var,p,options]; CreateFinFld[poly_,var_Symbol,p_Integer,options___] := \ Block[{thevar,alloptions,degree,orderFF,factsMultFF}, alloptions = Join[{options},Options[CreateFinFld]]; If[!PrimeQ[p],Message[CreateFinFld::notprime,p];Return[]]; If[Length[(thevar = Variables[poly])] != 1 || (thevar != var) || !PolynomialQ[poly,thevar], Message[CreateFinFld::notpoly]; Return[]]; If[!PolynomialQ[poly,thevar], Message[CreateFinFld::notpoly]; Return[]]; If[VerifyIrred/.alloptions, (* Check the polynomial for irreduc *) If[Head[Factor[poly,Modulus->p]] =!= Plus, Message[CreateFinFld::notirredpoly,poly,p]; Return[]]]; degree = Length[CoefficientList[poly,var]]-1; orderFF = p^degree; If[FactorOrder/.alloptions, (* Factor order of mult group - primitivity *) cunninghamFact[p^n-1]]; FinFld[p,degree,poly,var]]; CharacteristicFinFld[finfld_FinFld] := finfld[[1]]; DegreeFinFld[finfld_FinFld] := finfld[[2]]; SetAttributes[ModFinFld,Listable]; ModFinFld[elem_Integer] := elem; ModFinFld[elem_ElementFinFld] := \ Block[{elempoly,finfld,poly,char}, elempoly=elem[[1]]; finfld=elem[[2]]; poly=finfld[[3]]; char=finfld[[1]]; If[char==2, ElementFinFld[PolynomialMod[elempoly,poly,Modulus->char],finfld], (* else *) (* For other characteristics may need to do modular inversion of coefficients *) ElementFinFld[PolynomialMod[elempoly,poly,Modulus->char],finfld]/. (Rational[a_Integer,b_Integer] :> Mod[a*ExtendedGCD[b,char][[2,1]],char]) ] ]; Format[Literal[ModFinFld[elem_]],TeXForm] := StringJoin[ToString[TeXForm[elem[[1]]]], "(\hbox{mod }",ToString[TeXForm[elem[[2]][[3]]]],")"]; PlusFinFld::samefield="You can only add elements of the same field."; SetAttributes[PlusFinFld,{Listable,OneIdentity,Orderless}]; (* Note: While we also want Flat as an attribute, this leads *) (* to an infinite loop in the pattern match engine. *) PlusFinFld[] := 0; PlusFinFld[expr1_Integer] := expr1; PlusFinFld[expr1_ElementFinFld] := expr1; PlusFinFld[expr1_ElementFinFld,expr2_ElementFinFld] := \ Block[{}, If[expr1[[2]] =!= expr2[[2]], Message[PlusFinFld::samefield]; Return[$Failed]]; ModFinFld[ElementFinFld[expr1[[1]]+expr2[[1]],expr1[[2]]]] ]; PlusFinFld[expr1_Integer,expr2_ElementFinFld,expr3___] := \ PlusFinFld[ElementFinFld[expr1,expr2[[2]]],expr2,expr3]; PlusFinFld[expr1_ElementFinFld,expr2_ElementFinFld,expr3___] := \ PlusFinFld[PlusFinFld[expr1,expr2],expr3]; ElementFinFld/: Plus[x_ElementFinFld,y___] := PlusFinFld[x,y]; (* Overload x+y *) TimesFinFld::samefield="You can only multiply elements of the same field."; SetAttributes[TimesFinFld,{Listable,OneIdentity,Orderless}]; (* Note: While we also want Flat as an attribute, this leads *) (* to an infinite loop in the pattern match engine. *) TimesFinFld[] := 1; TimesFinFld[expr1_Integer] := expr1; TimesFinFld[expr1_ElementFinFld] := expr1; TimesFinFld[expr1_ElementFinFld,expr2_ElementFinFld] := \ Block[{}, If[expr1[[2]] != expr2[[2]], Message[TimesFinFld::samefield]; Return[$Failed]]; ModFinFld[ElementFinFld[expr1[[1]]*expr2[[1]],expr1[[2]]]] ]; TimesFinFld[expr1_Integer,expr2_ElementFinFld,expr3___] := \ TimesFinFld[ElementFinFld[expr1,expr2[[2]]],expr2,expr3]; TimesFinFld[expr1_ElementFinFld,expr2_ElementFinFld,expr3___] := \ TimesFinFld[TimesFinFld[expr1,expr2],expr3]; ElementFinFld/: Times[x_ElementFinFld,y___] := TimesFinFld[x,y]; (* Overload x*y *) SetAttributes[PowerModFinFld,{Listable}]; PowerModFinFld[expr_,0] := 1; PowerModFinFld[expr_,1] := expr; PowerModFinFld[expr_,exp_Integer?Negative] := PowerModFinFld[InverseFinFld[expr],-exp]; PowerModFinFld[expr_ElementFinFld,exp_Integer] := \ Block[{expdigits,accumul=1,i}, expdigits = IntegerDigits[exp,2]; For[i=1,i<=Length[expdigits],i++, accumul = accumul*accumul; If[expdigits[[i]] == 1, accumul = accumul*expr]; ]; accumul]; ElementFinFld/: Power[x_ElementFinFld,y_Integer] := PowerModFinFld[x,y]; SetAttributes[InverseFinFld,{Listable}]; (* Extended GCD for polynomials *) InverseFinFld[1] := 1; InverseFinFld[expr_ElementFinFld] := \ Block[{a=expr[[2]][[3]], (* minimum polynomial of field *) b=expr[[1]], (* polynomial of the given field element *) finfld=expr[[2]], (* the finite field *) char = expr[[2,1]], (* characteristic of the finite field *) var=expr[[2]][[4]], (* variable used in finite field repr *) v=1,u=0,z,q,r,sign=1}, While[Exponent[b,var] != 0, (* while b is not a constant *) q=PolynomialMod[PolynomialQuotient[a,b,var],char]; r=PolynomialMod[PolynomialRemainder[a,b,var],char]; z=q*v+u; a=b; b=r; u=v; v=z; sign=-sign]; ModFinFld[ElementFinFld[ExtendedGCD[sign*b,finfld[[1]]][[2,1]]*v,finfld]]]; FromListFinFld[coeff_List,ff_FinFld] := \ ElementFinFld[ Apply[Plus,Flatten[MapIndexed[(#1*(ff[[4]])^(#2-1))&,coeff]]], ff]; ToListFinFld[elt_ElementFinFld] := \ (Join[#,Table[0,{(elt[[2]][[2]]+1)-Length[#]}]])&[ CoefficientList[elt[[1]], elt[[2]][[4]]] ]; FromIntegerFinFld[n_Integer,finfld_FinFld] := \ FromListFinFld[ Reverse[IntegerDigits[n,finfld[[1]]]], finfld]; ToIntegerFinFld[elt_ElementFinFld] := \ elt[[1]]/.(elt[[2]][[4]])->(elt[[2]][[1]]); ListFinFld[finfld_FinFld] := \ Map[FromIntegerFinFld[#,finfld]&, Range[0,CharacteristicFinFld[finfld]^DegreeFinFld[finfld]-1]]; TraceFinFld[elt_ElementFinFld] := \ Sum[elt^(elt[[2]][[1]]^i),{i,0,elt[[2]][[2]]-1}]; MinPolyFinFld[n_Integer,var_Symbol] := var - n; MinPolyFinFld[elt_ElementFinFld,var_Symbol] := \ Block[{deg, char=elt[[2]][[1]], flddeg=elt[[2]][[2]], themat, thelist}, For[deg=1, deg<=flddeg, deg++, themat = Prepend[ Table[ToListFinFld[elt^i],{i,1,deg}], Prepend[Table[0,{flddeg}],1]]; thelist = NullSpace[Transpose[themat],Modulus->char]; If[Length[thelist] > 0, Break[]]; ]; Apply[Plus,Flatten[MapIndexed[(#1*var^(#2-1))&,thelist[[1]]]]] ]; FindIrred[n_Integer, p_Integer, var_Symbol] := \ Block[{thepoly}, For[i=p^n, ip]] == Plus, Break[]] ]; thepoly] PrimitiveFinFldQ[elt_ElementFinFld] := \ Block[{deg=elt[[2,2]],char=elt[[2,1]],order,factlist}, order = char^deg - 1; factlist = Transpose[cunninghamFact[order]][[1]]; Return[Apply[And,Map[(1!=elt^(order/#))&,factlist]]]]; ElementFinFld/:n_Integer == ElementFinFld[elt_,__] := n===elt; ElementFinFld/:n_Integer != ElementFinFld[elt_,__] := n=!=elt; ElementFinFld/:ElementFinFld[elt_,__] == n_Integer := n===elt; ElementFinFld/:ElementFinFld[elt_,__] != n_Integer := n=!=elt; ElementFinFld/:ElementFinFld[elt1_,ff_FinFld] == ElementFinFld[elt2_,ff_FinFld] := \ elt1 === elt2; ElementFinFld/:ElementFinFld[elt1_,ff_FinFld] != ElementFinFld[elt2_,ff_FinFld] := \ elt1 =!= elt2; (* If we factor the order of the multiplicative group (a Cunningham Number) *) (* we should remember it for future reference. *) cunninghamFact[n_Integer]:=cunninghamFact[n]=FactorInteger[n]; (**********************************************************************) Apply[Protect,Names["FinFld`*"]]; End[]; Print[Names["FinFld`*"]," have been defined in package FinFld."]; EndPackage[] (**********************************************************************)