(* Galois Field Package Version 1.2 September 10 1993 Copyright (c) 1992 by Ryoh Fuji-Hara and Misako Ebisawa This Package Impliments Finite Fields (Galois Fields) in Mathematica. There are four types of Galois Fields depending on constructions. (1) Prime field. (2) Extension field with a prime base field. (object loading) (3) Extension field with arbitrary base field. (object loading) (4) Extension field with arbitrary base field. User can select a type for ones application or hardware environment. This package is copyright 1992 by Ryoh Fuji-Hara and Misako Ebisawa. This package may be copied in its entirety for nonprofit purposes only. Sale, other than for the direct cost of the media, is prohibited. This copyright notice must accompany all copies. Ryoh Fuji-Hara Institute Socio-Economic Planning University of Tsukuba Tsukuba, Ibaraki, Japan 305 Phone:0298-53-5088 Fax: 0298-53-5070 E-mail: fujihara@shako.sk.tsukuba.ac.jp *) BeginPackage["GaloisField`"] AlgebraNames::usage = "AlgebraNames gives a list of algebra names which are defined till now."; AlgebraName::usage = "AlgebraName[x] gives the algebra name of variable 'x' which is declared on"; ExpAlgebraName::usage = "AlgebraName[x] gives the algebra name of expression 'x' which contains declared variables or constants."; DeclareGaloisField::usage = "DeclareGaloisField[field,n] declares a prime field , where the argument 'field' is an algebra name , 'n' is the order of the field. DeclareGaloisField[field] declares an extension field , where the argument 'field' is an algebra name. "; MakeGaloisField::usage = "MakeGaloisField[field,od,n,irp] makes an object of an extension field whose base field is the prime field of order 'od', where 'field' is an algebra name , 'n' is an extension degree, 'irp' is the coefficient list of a primitive irreducible polynomial, This function saves an object as a file with name 'field'. MakeGaloisField[field,bs,n,irp] makes an object of an extension field whose base field is 'od' , where 'field' is algebra name, 'bs' is base field name , 'n' is extension degree , 'irp' is the coefficient list of primitive irreducible polynomial over the base field. "; DeclareVariables::usage = "DeclareVariables[field,x1,x2 ... ] declares variables x1,x2 ... that you want to use in 'field', where 'field 'is a declared algebra name."; DeclareAlgebraicVariables::usage = DeclareIndeterminates::usage = "DeclareAlgebraicVariables[field,x1,x2 ... ] declares variables x1,x2 ... that you want to use in 'field', where 'field 'is a declared algebra name. These variables are also called indeterminates ."; ExponentRepresentation::usage = "ExponentRepresentation[elem,x] changes an element 'elem' of regular representation to exponent one expressed 'x' and returns it."; VectorRepresentation::usage = "VectorRepresentation[elem] changes an element 'elem' of regular represented to the vector representation and returns it."; RegularRepresentation::usage = "RegularRepresentation[field,elem] changes an element 'elem' of polynomial or vector representation to the regular one and returns it , where 'field' is algebra name."; PolynomialRepresentation::usage = "PolynomialRepresentation[elem,x] changes element 'elem' of regular representation to polynomial one with variable x and returns it."; ClearVariables::usage = "ClearVariables[x1, x2, ...] clears the variables x1, x2, ...which are declared. The variables may be algebraic variables."; ClearAlgebra::usage = "ClearAlgebra[field1,field2, ...] clears declared algebra names"; NonZero::usage = "NonZero[x1,x2,...] declares the declared variables as non zero valiavles"; NonZeroQ::usage = "NonZeroQ[x] gives 'true' if 'x' is declared as a non zero variable. "; GFVariables::usage = "GFVariables[field] gives all variales which are declared on the algebra 'field'."; GFAlgebraicVariables::usage = "GFAlgebraicVariables[field] gives the all algebraic variales which are declared on the algebra 'field'."; GFAllVariables::usage = "GFAllVariables gives the all variables which are declared in the Galois Field package."; GFAllAlgebraicVariables::usage = "GFAllAlgebraicVariables gives the all algebraic variables which are declared in the Galois Field package. "; NonZeroVariables::usage = "NonZeroVariables gives the all variables which are declared as non zero"; PolynomialEGCD::usage = PolynomialExtendedGCD::usage = "PolynomialEGCD[f1,f2] gives {a1,a2,d}, where d is gcd(f1,f2 with a relation a1 f1 + a2 f2 = d ."; PolynomialGCD::usage = "PolynomialGCD[poly1, poly2, ...] gives the greatest common divisor of the polynomials poly1, poly2, ... . PolynomialGCD[poly1, poly2, ..., Modulus->p] gives the GCD modulo the prime p. PolynomialGCD also works in the Galois Field Package."; Variables::usage = "Variables[expr] gives a list of all independent variables in a polynomial. In Galois Field Package, Variables does not list Galois field constant. "; Sqrt::usage = "Sqrt[z] gives the square root of z. Sqrt also works in the Galois Field Package."; SqrtMod::usage = "SqrtMod[d, n] is the square root of d (mod n), where n is a prime number."; SqrtMod::nres := "Warning: n has a prime factor p for which d is a nonresidue mod p."; Characteristic::usage = "Characteristic[field] gives characteristic of the finite field 'field'. "; IrreduciblePolynomial::usage = "IrreduciblePolynomial[field] gives, as a list, the irreducible polynomial which is used to extend the base field. "; BaseField::usage = "BaseField[field] gives the algebra name of the base field of 'field'."; ExtensionDegree::usage = "ExtensionDegree[field] gives extension degree of 'field' from its base field."; Order::usage = "Order[expr1, expr2] gives 1 if expr1 is before expr2 in canonical order, and -1 if expr1 is after expr2 in canonical order. It gives 0 if expr1 is identical to expr2. Order[field] gives order of 'field' in the Galois Field Package. Order[field[x]] gives the order of the element field[x] in the field 'field'."; ChToDecimal::usage = "ChToDecimal[{a1,a2,...}, b] gives decimal number which is transformed from b-base number {a1,a2,...}"; GFExponents::usage = "GFExponents[field] gives list of the elements of 'field' with exponent representation."; GFElements::usage = "GFElements[field] gives list of the elements of 'field' with regular representation."; PthRoot::usage = " PthRoof[ GFconstant ] gives p-th root of GFconstant."; ShiftRegister::usage = "ShiftRegister[x, y] shift right x and add a * y ,where a is the shifted out element. ShiftRegister[x, y, k ] gives the value of k times of ShiftRegister[x,y]."; Polynomialize::usage = "Polynomialize[list,v] is inverse process of CoefficentList."; CleanUp::usage = " CleanUp[a1,a2, ...] releases protection and remove symbols which contain a1 or a2 or ... "; Zero::usage = "The zero constant. "; PrimitiveQ::usage = "PrimitiveQ[x] gives True if x is primitive element in the field of x. x must be a finite field constant."; ZeroQ::usage = " ZeroQ[field,expr] returns true if the expression 'expr' is 0 or field[0] in a finite field, otherwise it returns false." OneQ::usage = "OneQ[field,expr] returns true if the expression 'expr' is 1 or field[1] in a finite field, otherwise it returns false." MinimalPolynomial::usage = " MinimalPolynomial[ a , x ] returns the minimal polynomial of the element a in a extension field with variable x. x shold be an algebraic variable over its base field. " (* ------- Options ---------------- *) Unprotect[DeclareVariables,ClearVariables]; Options[DeclareVariables] = {NonZero -> False }; Options[ClearVariables] = {RemoveVariables -> True }; (* ------------- Begin Context Private ------------------*) Begin["`Private`"] Unprotect[ AlgebraName ,GFElements ,AlgebraNames ,GFExponents ,BaseField ,GFVariables ,Characteristic ,IrreduciblePolynomial ,ChToDecimal ,MakeGaloisField ,CleanUp ,NonZero ,ClearAlgebra ,NonZeroQ ,ClearVariables ,NonZeroVariables ,DeclareAlgebraicVariables ,PolynomialEGCD ,DeclareGaloisField ,PolynomialExtendedGCD ,DeclareIndeterminates ,Polynomialize ,DeclareVariables ,PolynomialRepresentation ,ExpAlgebraName ,PthRoot ,ExponentRepresentation ,RegularRepresentation ,ExtensionDegree ,ShiftRegister ,GFAlgebraicVariables ,SqrtMod ,GFAllAlgebraicVariables ,VectorRepresentation ,GFAllVariables,Order ,Zero ,PrimitiveQ ,Order ,ZeroQ ,OneQ ,MinimalPolynomial ]; AlgebraNames = {}; GFAllVariables = {}; GFAllAlgebraicVariables = {}; NonZeroVariables = {}; Attributes[AlgebraName] = {Listable}; Attributes[PthRoot] = {Listable}; Attributes[Zero] = {Constant}; Attributes[VectorRepresentation] = {Listable}; Attributes[NonZeroQ] = {Listable}; Attributes[Order] = {Listable}; Attributes[PrimitiveQ] = {Listable}; Zero /: Plus[Zero,0] := Zero; Zero /: Plus[Zero,Zero] := Zero; Zero /: Plus[Zero,x_] := x ; Zero /: Times[Zero,x_] := Zero; Zero /: Power[Zero,x_Integer] := Zero /; x >=1 ; Zero /: Power[x_Integer, Zero] := 1 /; x != 0; Zero /: Power[Zero,0] := 0^Zero ; Zero /: Power[Zero,Zero] := 0^Zero ; (* ------------- Declare Galois Field Type I ---------------- *) DeclareGaloisField[field_Symbol,num_Integer] := (* This is used to declare a prime field *) Block[ {ad,mlt,pow,vQ,cQ,alvQ,nzvQ,x,y}, Off[General::spell1]; If[ MemberQ[AlgebraNames,field], Return[Print[ field," has already been declared."]], Null ]; UnprotectAlgebra[field]; field /: GFVariables[field] = {}; field /: GFAlgebraicVariables[field] = {}; (* --- generate operator names --- *) ad=ToExpression[StringInsert["Addition",ToString[field],-1]]; mlt=ToExpression[StringInsert["Multiple",ToString[field],-1]]; pow=ToExpression[StringInsert["Power",ToString[field],-1]]; vQ=ToExpression[StringInsert["VQ",ToString[field],2]]; cQ=ToExpression[StringInsert["ConQ",ToString[field],4]]; alvQ=ToExpression[StringInsert["AlVQ",ToString[field],4]]; nzvQ=ToExpression[StringInsert["NZVQ",ToString[field],4]]; field /: Attributes[field] = {Constant, Listable}; field /: Characteristic[field] = num; field /: Order[field] = num; field /: ExtensionDegree[field] = 1; field /: BaseField[field] = None; Unprotect[AlgebraNames]; AlgebraNames = Append[AlgebraNames,field]; Protect[AlgebraNames]; (* --- ganerate Addition , Multiplication , Power --- *) ad[x_Integer,y_Integer] = Mod[x+y,num]; mlt[x_Integer,y_Integer] = Mod[x*y,num]; pow[x_Integer,y_Integer] = Mod[x^y,num]; MakeOperators[field,ad,mlt,pow,vQ,cQ,alvQ,nzvQ]; field /: Sqrt[ field[0] ] := 0; field /: Sqrt[ field[1] ] := field[1] ; field /: Power[field[x_Integer], 1/2 ] := field[ SqrtMod[x,Order[field]] ] /; JacobiSymbol[x,Order[field]]==1; field /: PthRoot[ field[x_] ] := field[x] ; Protect[ Evaluate[field]]; Print[field," was declared."]; Print[" Order is ",Order[field]]; Print[" Characteristic is ",Characteristic[field] ]; ]; (* ======= Declarelation of Type II Galois Field ====== *) DeclareGaloisField[field_Symbol] := (* This is used to declare an extension field *) Block[{bs}, Off[General::spell1]; Off[Order::argr]; If[MemberQ[AlgebraNames,field], Return[Print[ field," has already been declared."]] , Null ]; (* Check existing of the file 'field' . *) If[FileNames[ToString[field],$Path]=={}, Print["Galois field object '",field,"' does not exist."]; Return[]; , UnprotectAlgebra[field]; Unprotect[ChToDecimal,AlgebraNames]; Get[ToString[field]]; ]; field /: GFVariables[field] = {}; field /: GFAlgebraicVariables[field] = {}; field /: Attributes[field] = {Constant,Listable}; AlgebraNames = Append[AlgebraNames,field]; MakeOperators[field,ad,mlt,pow,vQ,cQ,alvQ,nzvQ]; bs = BaseField[field]; Protect[ Evaluate[field],ChToDecimal,AlgebraNames]; Print[field," was declared."]; Print[" Order is ",Order[field]]; Print[" Characteristic is ",Characteristic[field] ]; Print[" Irreducible Polynomial is ", IrreduciblePolynomial[field] ]; Print[" Base Field is ",BaseField[field] ]; Print[" Extension Degree is ",ExtensionDegree[field] ] ; If[Characteristic[field]^ExtensionDegree[field]==Order[field], DeclareGaloisField[bs,Characteristic[field]], DeclareGaloisField[bs] ] ]; (* ======= Declarelation of Type IV Galois Field ====== *) DeclareGaloisField[field_Symbol,bs_Symbol,n_Integer,irp_List]:= Block[{}, Off[General::spell1]; Off[Order::argr]; If[ MemberQ[AlgebraNames,field], Return[Print[ field," has already been declared."]] , Null ]; If[ MemberQ[AlgebraNames,bs], Print[bs," has already been declared."] , Print[bs," has not been declared."]; Return[Print[field," can not be declared."]]; ]; UnprotectAlgebra[field]; field /: GFVariables[field] = {}; field /: GFAlgebraicVariables[field] = {}; (* --- generate operator names --- *) ad=ToExpression[StringInsert["Addition",ToString[field],-1]]; mlt=ToExpression[StringInsert["Multiple",ToString[field],-1]]; pow=ToExpression[StringInsert["Power",ToString[field],-1]]; vQ=ToExpression[StringInsert["VQ",ToString[field],2]]; cQ=ToExpression[StringInsert["ConQ",ToString[field],4]]; alvQ=ToExpression[StringInsert["AlVQ",ToString[field],4]]; nzvQ=ToExpression[StringInsert["NZVQ",ToString[field],4]]; field /: Attributes[field] = {Constant, Listable}; field /: Characteristic[field] = Characteristic[bs]; field /: Order[field] = Order[bs]^n; field /: BaseField[field] = bs; field /: ExtensionDegree[field] = n; field /: IrreduciblePolynomial[field] = irp; (* Apply[Plus,irp*Table[x^i,{i,0,Length[irp]-1}]];*) Unprotect[AlgebraNames]; AlgebraNames = Append[AlgebraNames,field]; Protect[AlgebraNames]; (* --- ganerate Addition , Multiplication , Power --- *) ad[x_Integer,y_Integer] := Block[{a,b,lstab,answer,ans,prelstab,q}, b=Map[bs,IntegerDigits[y,Order[bs],ExtensionDegree[field]]]; a=Map[bs,IntegerDigits[x,Order[bs],ExtensionDegree[field]]]; prelstab=a+b; lstab=prelstab /. bs[q_]->q; ans=ChToDecimal[lstab,Order[bs]]; answer=Map[field,ans]; answer ]; mlt[z_Integer,y_Integer] := Block[{a,b,lstab,answer,irrepo,remlst,q}, DeclareAlgebraicVariables[bs,innerx]; b=Map[bs,IntegerDigits[y,Order[bs],ExtensionDegree[field]]]; a=Map[bs,IntegerDigits[z,Order[bs],ExtensionDegree[field]]]; tt=Table[innerx^i,{i,0,Length[b]-1}] /.field[q_]->q; pb=Apply[Plus,tt*Reverse[b]]; pa=Apply[Plus,tt*Reverse[a]]; irrepo=PolynomialRepresentation[bs[irp],innerx] ; remlst=CoefficientList[PolynomialRemainder[ Expand[pa*pb],irrepo,innerx],innerx] /.bs[q_]->q; answer=Map[field,ChToDecimal[Reverse[remlst],Order[bs]]]; answer ]; pow[z_Integer,y_Integer] := Block[{a,tt,pa,irrepo,remlst,answer,q}, DeclareAlgebraicVariables[bs,innerx]; a=Map[bs,IntegerDigits[z,Order[bs],ExtensionDegree[field]]]; tt=Table[innerx^i,{i,0,Length[a]-1}] /.field[q_]->q; pa=Apply[Plus,tt*Reverse[a]]; irrepo=PolynomialRepresentation[bs[irp],innerx] ; remlst=CoefficientList[PolynomialRemainder[ Expand[pa^y],irrepo,innerx],innerx] /.bs[q_]->q; answer=Map[field,ChToDecimal[Reverse[remlst],Order[bs]]]; answer ]; MakeOperators[field,ad,mlt,pow,vQ,cQ,alvQ,nzvQ]; Protect[ Evaluate[field]]; Print[field," was declared."]; Print[" Order is ",Order[field]]; Print[" Characteristic is ",Characteristic[field] ]; Print[" Irreducible Polynomial is ", IrreduciblePolynomial[field] ]; Print[" Base Field is ",BaseField[field] ]; Print[" Extension Degree is ",ExtensionDegree[field] ]; ]; (* ------------- Make Galois Field , Type II ---------------- *) MakeGaloisField[field_Symbol,od_Integer,n_Integer,irp_List] := Block[{var,i,l,m,an,ad,mlt,pow,ex,ele,irp2,l1, addi,multi,pwe,vQ,cQ,alvQ, p,f,fname,}, fname=ToString[field]; If[FileNames[fname]=!={}, Print["Galois field object '",field,"' already exists."]; Print[field," can not be made."]; Return[]; ,]; (* If file 'field' dose not exist, following program makes file and save it. *) field /: Characteristic[field] = od; field /: Order[field] = od^n; field /: ExtensionDegree[field] = n; field /: IrreduciblePolynomial[field] = irp; field /: BaseField[field] = ToExpression[StringJoin["GF",ToString[od]]]; addi=ToExpression[StringInsert["Addition",ToString[field],-1]]; multi=ToExpression[StringInsert["Multiple",ToString[field],-1]]; pwe=ToExpression[StringInsert["Power",ToString[field],-1]]; vQ=ToExpression[StringInsert["VQ",ToString[field],2]]; cQ=ToExpression[StringInsert["ConQ",ToString[field],4]]; alvQ=ToExpression[StringInsert["AlVQ",ToString[field],4]]; ad=addi; mlt=multi; pow=pwe; Save[fname,ad,mlt,pow,vQ,cQ,alvQ]; irp2 = Mod[-Delete[irp,n+1], od]; ex=Table[0,{Order[field]-1}]; ele={0,1}; PrependTo[ex,Infinity]; l = Table[0, {n}]; l[[1]] = 1; For[i=1,i<= Order[field]-2,i++, l = RotateRight[l]; l1 = l[[1]]; l[[1]] = 0; l = Mod[ l + l1 * irp2, od]; m=ChToDecimal[Reverse[l],od]; ex[[m+1]]=i; AppendTo[ele,m]; ]; field/: GFExponents[field] = ex; field/: GFElements[field] = ele; (* This makes only operator Addition since it is based on its base field. The rest of operators , Multiple Power, and so on , are made in the function MakeOtherOperator. *) addi[x_Integer,y_Integer] := Block[{lstab}, lstab=Mod[IntegerDigits[y,od,n]+IntegerDigits[x,od,n],od]; Return[ChToDecimal[lstab,od]]; ]; MakeOtherOperator[field,multi,pwe]; Save[fname,field,addi,multi,pwe]; ClearAll[Evaluate[field],Evaluate[addi],Evaluate[multi],Evaluate[pwe]]; Print[" Galois field object '",field, "' was saved."]; ClearAlgebra[field]; ]; (* MakeGaloisField *) (* --------------- Make Galois Field, Type III ---------------- *) MakeGaloisField[field_Symbol,bs_Symbol,n_Integer,irp_List] := Block[{var,i,l,m,an,highestdegreepolynomial,ad,mlt,pow,ex,ele, addi,multi,pwe,vQ,cQ,alvQ,irp2,l1,a, rightsidepolynomial,p,poly,innerx,f,fname,polylist={1}}, If[MemberQ[AlgebraNames,field], Print[field," has been declared."]; Print[field," can not be made."]; Return[]; ,]; If[ MemberQ[AlgebraNames,bs], Null , Print[bs," has not been declared."]; Print[field," can not be made."]; Return[]; ]; (* Check existing of the file 'field'. *) fname=ToString[field]; If[FileNames[fname]=!={}, Print["The file ",field," exists."]; Print[field," can not be saved."]; Return[]; ,]; field /: Characteristic[field] = Characteristic[bs]; field /: Order[field] = Order[bs]^n; field /: BaseField[field] = bs; field /: ExtensionDegree[field] = n; field /: IrreduciblePolynomial[field] = irp; addi=ToExpression[StringInsert["Addition",ToString[field],-1]]; multi=ToExpression[StringInsert["Multiple",ToString[field],-1]]; pwe=ToExpression[StringInsert["Power",ToString[field],-1]]; vQ=ToExpression[StringInsert["VQ",ToString[field],2]]; cQ=ToExpression[StringInsert["ConQ",ToString[field],4]]; alvQ=ToExpression[StringInsert["AlVQ",ToString[field],4]]; ad=addi; mlt=multi; pow=pwe; Save[fname,ad,mlt,pow,vQ,cQ,alvQ]; irp2= -bs[Delete[irp,n+1] ]; ex=Table[0,{Order[field]-1}]; ele={0,1}; PrependTo[ex,Infinity]; l = bs[ Table[0,{n}] ]; l[[1]] = bs[1]; For[i=1,i<=Order[field]-2,i++, l = RotateRight[l]; l1 = l[[1]]; l[[1]] = bs[0]; l = l + l1 * irp2; m=ChToDecimal[Reverse[l] /. bs[a_]->a ,Order[bs]]; ex[[m+1]]=i; AppendTo[ele,m]; ]; field /: GFExponents[field] = ex; field /: GFElements[field] = ele; (* --- Addition --- *) addi[x_Integer,y_Integer] := Block[{a,b,q}, b=bs[IntegerDigits[y,Order[bs],ExtensionDegree[field]]]; a=bs[IntegerDigits[x,Order[bs],ExtensionDegree[field]]]; Return[ ChToDecimal[a+b /. bs[q_]->q ,Order[bs]] ]; ]; MakeOtherOperator[field,multi,pwe]; Save[fname,field,addi,multi,pwe]; ClearAll[Evaluate[field],Evaluate[addi],Evaluate[multi],Evaluate[pwe]]; Print[" Galois field object '",field, "' was saved."]; ClearAlgebra[field]; ]; (* MakeGaloisField *) (* ------------ Make Operators ------------ *) MakeOperators[field_,ad_,mlt_,pow_,vQ_,cQ_,alvQ_,nzvQ_] := Block[{x,y,z,n,m}, Unprotect[ DeclareVariables,DeclareAlgebraicVariables, NonZero,NonZeroQ,AlgebraName,DeclareIndeterminates,PthRoot]; DeclareVariables[field,z__,opts___Rule] := Block[{incrm,sym,opt,RemoveVariables}, opt = NonZero /. {opts} /. Options[DeclareVariables]; sym=Flatten[{z}]; Unprotect[Evaluate[vQ],Evaluate[nzvQ],AlgebraName, GFAllVariables,GFVariables]; For[incrm=1,incrm<=Length[sym],incrm++, If[ MemberQ[GFAllAlgebraicVariables,sym[[incrm]]] || NonZeroQ[ sym[[incrm]] ] , ClearVariables[sym[[incrm]],RemoveVariables -> False ]; Unprotect[AlgebraName,GFVariables,GFAllVariables, Evaluate[vQ],Evaluate[field] ]; ,]; AlgebraName[Evaluate[sym[[incrm]]]] = field; vQ[Evaluate[sym[[incrm]]]] = True; vQ[Plus[Evaluate[sym[[incrm]]],_]] = True; vQ[Times[Evaluate[sym[[incrm]]],_]] = True; vQ[Power[Evaluate[sym[[incrm]]],_]] = True; ]; Unprotect[Evaluate[field]]; field /: GFVariables[field] = Union[ GFVariables[field],sym]; GFAllVariables = Union[GFAllVariables, sym]; If[opt, NonZero[z] , ]; Protect[Evaluate[field],Evaluate[vQ],Evaluate[nzvQ],AlgebraName, GFAllVariables,GFVariables]; ]; DeclareAlgebraicVariables[field,z__] := Block[{incrm,sym,RemoveVariables}, sym=Flatten[{z}]; Unprotect[Evaluate[field],Evaluate[alvQ],AlgebraName, GFAllAlgebraicVariables,GFAlgebraicVariables]; Unprotect[z]; For[incrm=1,incrm<=Length[sym],incrm++, If[MemberQ[GFAllVariables,sym[[incrm]] ] , ClearVariables[ sym[[incrm]] ,RemoveVariables -> False] ; Unprotect[AlgebraName,GFAlgebraicVariables, Evaluate[field], Evaluate[sym[[incrm]]],Evaluate[alvQ], GFAllAlgebraicVariables]; ,]; AlgebraName[Evaluate[sym[[incrm]]]] = field; Evaluate[sym[[incrm]]]/: alvQ[Evaluate[sym[[incrm]]]] = True; alvQ[Plus[Evaluate[sym[[incrm]]],_]] = True; alvQ[Times[Evaluate[sym[[incrm]]],_]] = True; alvQ[Power[Evaluate[sym[[incrm]]],_]] = True; ]; field /: GFAlgebraicVariables[field] = Union[GFAlgebraicVariables[field],sym]; GFAllAlgebraicVariables = Union[GFAllAlgebraicVariables, sym]; Protect[Evaluate[field],Evaluate[alvQ],AlgebraName, GFAllAlgebraicVariables,GFAlgebraicVariables]; Protect[Evaluate[ sym ]]; ]; DeclareIndeterminates = DeclareAlgebraicVariables; (* -- *) Unprotect[Evaluate[cQ],Evaluate[vQ],Evaluate[alvQ],Evaluate[nzvQ]]; cQ[ field[n_]] := True; cQ[ Plus[field[n_], _]] := True; cQ[ Times[field[n_], _]] := True; cQ[ Power[field[n_], _]] := True; (* cQ[ Plus[x_?cQ,_] ] := True; cQ[ Times[x_?cQ,_] ] := True; cQ[ Power[x_?cQ,_] ] := True; *) vQ[Plus[x_?vQ,_]] := True; vQ[Times[x_?vQ,_]] := True; vQ[Power[x_?vQ,_]] := True; alvQ[Plus[x_?alvQ,_]] := True; alvQ[Times[x_?alvQ,_]] := True; alvQ[Power[x_?alvQ,_]] := True; nzvQ[Power[x_?nzvQ,_]] := True; Protect[Evaluate[cQ],Evaluate[vQ],Evaluate[alvQ],Evaluate[nzvQ]]; (* ----- Plus , Times , Power ----- *) field[x_Integer] := Print[field,"[",x,"] is not an element of ",field] /; x >= Order[field]; field/: Plus[field[y_Integer],field[z_Integer]] := Block[{Wad}, Wad := ad[y,z]; If[ Wad == 0, 0, field[ad[y,z]] ] ]; field/: Plus[y_Integer,field[z_Integer]] := field[ad[Mod[y,Characteristic[field]],z]]; field/: Plus[field[0],x_] := x; Unprotect[Plus]; Plus[Times[x_,field[n_]],Times[x_,field[m_]]] := field[ad[n,m]]*x; Plus[x_,Times[x_,field[y_]]] := field[ad[1,y]]*x; Protect[Plus]; field/: Plus[BaseField[field][y_Integer],field[z_Integer]] := field[y] + field[z]; field/: Times[field[0],x_] := 0 /; vQ[x] || alvQ[x]; field/: Times[field[0],field[x_Integer]] :=0; field/: Times[Indeterminate, field[0]] := Indeterminate; field/: Times[x_Symbol,field[1]] := x; field/: Times[x_Power,field[1]] := x; field/: Times[field[y_Integer],field[z_Integer]] := field[mlt[y,z]]; field/: Times[x_Integer,field[y_Integer]] := field[Mod[x,Characteristic[field]]]*field[y]; field/: Times[BaseField[field][y_Integer],field[z_Integer]] := field[y] field[z]; Unprotect[Times]; Times[x_Integer,y_] := field[Mod[x,Characteristic[field]]]*y /; vQ[y] || alvQ[y] ; Times[Rational[1, n_],x_] := x * field[ Mod[n,Characteristic[field]]]^-1 /; cQ[x] || vQ[x]; Protect[Times]; field/: Power[field[0],y_Integer] := If[ y > 0, Return[0] , Print["Power:",field,"[0]^-1 and ", field,"[0]^0 are undefined"]; Return[Indeterminate] ]; field/: Power[field[x_Integer],y_Integer] := Block[{a}, a=Mod[y,Order[field]-1]; If[a==0, field[1] , field[pow[x,a]] ] ]; field/: Equal[field[x_Integer],0] := Equal[x,0]; field/: Equal[0,field[x_Integer]] := Equal[x,0]; field/: Equal[field[x_Integer],1] := Equal[x,1]; field/: Equal[1,field[x_Integer]] := Equal[x,1]; field/: Unequal[field[x_Integer],0] := Unequal[x,0]; field/: Unequal[0,field[x_Integer]] := Unequal[x,0]; field/: Unequal[field[x_Integer],1] := Unequal[x,1]; field/: Unequal[1,field[x_Integer]] := Unequal[x,1]; AlgebraName[ field[x_] ] := field ; Unprotect[Power,Zero]; field /: Power[field[x_Integer],Zero] := field[1] /; x>=1; If[Order[field]==2, Power[x_,Zero] := field[1] /; nzvQ[x] && vQ[x]; Power[x_,0] := x^Zero /; vQ[x] ; Power[x_,y_Integer] := x /; vQ[x] && y>1; Power[x_,y_Integer] := x^-1 /; vQ[x] && y<-1; Power[x_,0] := field[1] /; alvQ[x] ; , Power[x_,0] := field[1] /; nzvQ[x] && vQ[x]; Power[x_,(Order[field]-1)] := field[1] /; nzvQ[x] && vQ[x]; Power[x_,0] := x^Zero /; vQ[x] ; Power[x_,Zero] := field[1] /; nzvQ[x]; Power[x_,0] := field[1] /; alvQ[x] ; Power[x_,Zero] := field[1] /; alvQ[x] ; Power[x_,y_Integer] := x^(Mod[y-1,Order[field]-1]+1) /; vQ[x] && y>=Order[field]; Power[x_,y_Integer] := x^-(Mod[Abs[y]-1,Order[field]-1]+1) /; vQ[x] && y <= -Order[field]; ]; Protect[Power,Zero]; If[ ExtensionDegree[field] >= 2, field /: Power[field[y_Integer], 1/2 ] := Block[{a,b}, a=GFExponents[field][[y+1]]; If[OddQ[a], b=(a+Order[field]-1)/2; Return[field[GFElements[field][[b+2]]]], Return[field[GFElements[field][[(a/2)+2]]]] ] ] /; Characteristic[field] == 2 ; field /: Power[field[x_Integer], 1/2 ] := field[GFElements[field][[Divide[GFExponents[field][[x+1]],2]+2]] ] /; EvenQ[GFExponents[field][[x+1]] ] ; ,]; field /: Power[field[0], 1/2 ] := 0; field /: Power[field[1], 1/2 ] := field[1]; field /: PthRoot[field[0]] = 0; PthRoot[0] = 0; field /: PolynomialRemainder[poly_,field[0],x_]:= Print["PolynomialRemainder: can not devide by ",field[0] ]; (* ----- Variables ----- *) Unprotect[Variables]; Variables[Power[z_,x_]] := Union[Variables[z],Variables[x]]; Variables[Times[z_,x_]] := Union[Variables[z],Variables[x]]; Variables[Plus[z_,x_]] := Union[Variables[z],Variables[x]]; Variables[z_] := Block[{}, Return[ Variables[z //. field[a_]->1] ]; ] /; cQ[z]; Protect[Variables]; field /: Variables[field,z_] := Block[ {vari}, vari = Variables[z] /. field[a_] -> 1; Return[ Complement[ vari, {1} ] ]; ]; field /: ZeroQ[field, expr_ ] := expr === 0 || expr === field[0] ; field /: OneQ[field, expr_ ] := expr === 1 || expr === field[1] ; Protect[ Evaluate[aln],Evaluate[ad], Evaluate[mlt], Evaluate[pow]]; Protect[ DeclareVariables,DeclareAlgebraicVariables, NonZero,NonZeroQ,AlgebraName,DeclareIndeterminates,PthRoot]; ]; (* MakeOperators *) (* -------------------- Libraries -------------------- *) MakeFunctionNames[field_] := Block[{}, addi=ToExpression[StringInsert["Addition",ToString[field],-1]]; multi=ToExpression[StringInsert["Multiple",ToString[field],-1]]; pwe=ToExpression[StringInsert["Power",ToString[field],-1]]; vQ=ToExpression[StringInsert["VQ",ToString[field],2]]; cQ=ToExpression[StringInsert["ConQ",ToString[field],4]]; alvQ=ToExpression[StringInsert["AlVQ",ToString[field],4]]; ]; MakeOtherOperator[field_,multi_,pwe_] := Block[{}, field/: Sqrt[field[y_Integer]] := Block[{a,b}, a=GFExponents[field][[y+1]]; If[OddQ[a], b=(a+Order[field]-1)/2; Return[field[GFElements[field][[b+2]]]], Return[field[GFElements[field][[(a/2)+2]]]] ] ] /; Characteristic[field] == 2 ; field/: Sqrt[field[y_Integer]] := field[GFElements[field][[Divide[GFExponents[field][[y+1]],2]+2]] ] /; EvenQ[GFExponents[field][[y+1]] ] ; field /: Sqrt[ field[0] ] := 0; field /: Sqrt[ field[1] ] := field[1]; multi[y_Integer,z_Integer] := GFElements[field][[Mod[GFExponents[field][[y+1]]+ GFExponents[field][[z+1]],Order[field]-1]+2]]; pwe[x_Integer,y_Integer] := GFElements[field][[Mod[GFExponents[field][[x+1]]*y, Order[field]-1]+2]] ; ]; (* MakeOtherOperator *) DeclareVariables[alname_] := Return[GFVariables[alname]]; DeclareVariables[] := Return[GFAllVariables]; DeclareAlgebraicVariables[alname_] := Return[GFAlgebraicVariables[alname]]; DeclareAlgebraicVariables[] := Return[GFAllAlgebraicVariables]; DeclareGaloisField[] := Return[AlgebraNames]; AlgebraName[Plus[exp_,_]] := AlgebraName[exp]; AlgebraName[Times[exp_,_]] := AlgebraName[exp]; AlgebraName[Power[exp_,_]] := AlgebraName[exp]; AlgebraName[f_[exp_]] := AlgebraName[exp]; ExpAlgebraName = AlgebraName; ClearVariables[x__, opts___Rule] := Block[ { sym, incrm,vari,alvari,alvQ,vQ,nzvQ, addi,multi,pwe,cQ,opt}, opt = RemoveVariables /. {opts} /. Options[ClearVariables]; sym = Flatten[{x}]; MakeFunctionNames[aln]; nzvQ=ToExpression[StringInsert["NZVQ",ToString[aln],4]]; Unprotect[Evaluate[vQ],Evaluate[alvQ],Evaluate[nzvQ] , GFVariables,GFAllVariables,AlgebraName, GFAlgebraicVariables,GFAllAlgebraicVariables,NonZeroVariables]; For[incrm=1,incrm<=Length[sym],incrm++, vari = sym[[incrm]]; If[MemberQ[GFAllVariables,vari], alvari = AlgebraName[vari]; Unprotect[Evaluate[alvari],Evaluate[vari]]; Evaluate[alvari] /: GFVariables[alvari ] = Complement[GFVariables[alvari],{vari} ]; Unprotect[GFAllVariables]; GFAllVariables = Complement[GFAllVariables,{vari} ]; ClearAll[ Evaluate[vari] ]; ,]; If[MemberQ[GFAllAlgebraicVariables,vari], alvari = AlgebraName[vari]; Unprotect[Evaluate[alvari],Evaluate[vari]]; Evaluate[alvari] /: GFAlgebraicVariables[alvari ] = Complement[GFAlgebraicVariables[alvari],{vari} ]; GFAllAlgebraicVariables = Complement[GFAllAlgebraicVariables,{vari}]; ClearAll[ Evaluate[vari] ]; ,]; If[NonZeroQ[vari], NonZeroVariables = Complement[NonZeroVariables,{ vari}]; Unprotect[Evaluate[alvari],Evaluate[vari]]; ClearAll[ Evaluate[vari] ]; ,]; Protect[Evaluate[alvari],]; If[opt , Print[vari , " was removed."]; Remove[ Evaluate[vari] ] ; , ]; ]; (*For *) Protect[GFVariables,GFAllVariables,AlgebraName, GFAlgebraicVariables,GFAllAlgebraicVariables,NonZeroVariables, Evaluate[vQ],Evaluate[alvQ],Evaluate[nzvQ], ]; ]; (* ClearVariables *) ClearAlgebra[ alnames__ ] := Block[ {sym, incrm ,aln, addi,multi,pwe,cQ,vQ,alvQ,nzvQ}, sym = Flatten[ {alnames} ]; For[incrm=1,incrm<=Length[sym],incrm++, aln = sym[[incrm]]; Unprotect[ Evaluate[aln],GFVariables,GFAlgebraicVariables]; If[ MemberQ[AlgebraNames,aln], GFVariables[aln] ={}; GFAlgebraicVariables[aln] ={}; Unprotect[AlgebraNames]; AlgebraNames = Complement[AlgebraNames, {aln}]; Protect[AlgebraNames]; ,]; ClearAll[ Evaluate[aln] ]; MakeFunctionNames[aln]; nzvQ=ToExpression[StringInsert["NZVQ",ToString[aln],4]]; Unprotect[ Evaluate[addi], Evaluate[multi], Evaluate[pwe],Evaluate[cQ],Evaluate[vQ], Evaluate[alvQ],Evaluate[nzvQ] ]; Remove[ Evaluate[addi], Evaluate[multi],Evaluate[pwe], Evaluate[cQ],Evaluate[vQ],Evaluate[alvQ], Evaluate[nzvQ] ]; Remove[ Evaluate[aln] ]; Protect[GFVariables,GFAlgebraicVariables]; ]; (* For *) ]; (* ClearAlgebra *) UnprotectAlgebra[ aln_] := Block[ {addi,multi,pwe,cQ,vQ,alvQ,nxvQ }, Unprotect[ Evaluate[aln]]; MakeFunctionNames[aln]; nzvQ=ToExpression[StringInsert["NZVQ",ToString[aln],4]]; Unprotect[ Evaluate[addi], Evaluate[multi], Evaluate[pwe],Evaluate[cQ],Evaluate[vQ], Evaluate[alvQ],Evaluate[nzvQ] ]; ]; CleanUp[alns__ ] := Block[ {aln,i,alnames,addi,multi,pwe,cQ,vQ,alvQ,nxvQ}, alnames = Flatten[{alns}]; For[i=1,i<=Length[alnames],i++, aln = alnames[[i]]; Unprotect[Evaluate[aln] ]; ClearAll[ Evaluate[aln] ]; MakeFunctionNames[aln]; nzvQ=ToExpression[StringInsert["NZVQ",ToString[aln],4]]; Unprotect[ Evaluate[addi], Evaluate[multi], Evaluate[pwe],Evaluate[cQ],Evaluate[vQ], Evaluate[alvQ],Evaluate[nzvQ] ]; Remove[ Evaluate[addi], Evaluate[multi], Evaluate[pwe],Evaluate[cQ],Evaluate[vQ], Evaluate[alvQ],Evaluate[nzvQ] ]; Remove[ Evaluate[aln] ]; ]; ]; NonZero[z__] := Block[{incrm,sym,alname,nzvQ}, sym=Flatten[{z}]; Unprotect[NonZeroVariables]; NonZeroVariables = Union[NonZeroVariables, sym]; Protect[NonZeroVariables]; For[incrm=1,incrm<=Length[sym],incrm++, If[MemberQ[GFAllVariables, sym[[incrm]] ], , Return[Print[sym[[incrm]], " is not declared."]] ]; alname = AlgebraName[sym[[incrm]] ]; nzvQ=ToExpression[StringInsert["NZVQ",ToString[alname],4]]; Unprotect[Evaluate[nzvQ]]; Evaluate[sym[[incrm]]]/: nzvQ[Evaluate[sym[[incrm]]]] = True; nzvQ[Power[Evaluate[sym[[incrm]]],_]] = True; Protect[Evaluate[nzvQ] ]; ]; ]; NonZeroQ[z_] := MemberQ[NonZeroVariables, z]; NonZero[] := NonZeroVariables; End[]; (* -------------------- Utilities -------------------- *) Begin["`Utilities`"]; ChToDecimal[z_List,ob_Integer] := Block[{decri,zl,con=0,base=1}, zl=Length[z]; For[decri=zl,decri>=1,decri--, con=base * z[[decri]] + con; base = base * ob ]; Return[con] ] ; ExponentRepresentation[z_[0],w_Symbol] := Print[w,"^Infinity"]; ExponentRepresentation[z_,w_Symbol] := Block[{headname,nandemo,numb}, headname=Head[z]; If[ ListQ[GFExponents[headname]], , Print["dose not work in this field."]; Return[]; ]; DeclareVariables[headname,w]; numb=z /.headname[nandemo_]->nandemo ; Return[ w^GFExponents[headname][[numb+1]] ]; ]; VectorRepresentation[z_] := Block[{headname,nandemo,veckotae,numb,increm}, headname=Head[z]; numb=z /.headname[nandemo_]->nandemo ; If[ExtensionDegree[headname] <= 1, Print["VectorRepresentation is not available for ",headname]; Return[]; , ]; veckotae=Reverse[IntegerDigits[numb, Order[BaseField[headname]],ExtensionDegree[headname]]]; Return[veckotae] ]; Attributes[VectorRepresentation] = {Listable}; (* Attributes[PolynomialRepresentation] = {Listable}; *) PolynomialRepresentation[z_List,w_Symbol] := Block[{tab,polyans}, tab=Table[w^i,{i,0,Length[z]-1}]; Return[Apply[Plus,z*tab]]; ]; PolynomialRepresentation[z_,w_Symbol] := Block[{vechyougen,hensuu,headname,polyanswer}, If[MemberQ[AlgebraNames, BaseField[Head[z]] ],, Print[" does not work in this field."]; Return[]; ]; vechyougen=VectorRepresentation[z]; headname=BaseField[Head[z]]; Clear[w]; DeclareAlgebraicVariables[headname,w]; hensuu=Table[w^i,{i,0,Length[vechyougen]-1}] ; Return[Apply[Plus,headname[vechyougen]*hensuu]]; ] /; TrueQ[Head[z]=!=List] ; (* RegularRepresentation[Power[z_,Infinity],alg_] := alg[0]; *) RegularRepresentation[alg_,0] := alg[0]; RegularRepresentation[alg_,1] := alg[1]; RegularRepresentation[alg_,z_Symbol] := alg[GFElements[alg][[3]] ]; RegularRepresentation[alg_,Power[z_,w_]] := Block[ {ww}, If[ ListQ[GFElements[alg]], , Print["dose not work in this field."]; Return[]; ]; ww = Mod[w, Order[alg]-1]; Return[ alg[GFElements[alg][[ww+2]] ] ]; ]; RegularRepresentation[alg_,z_Plus] := Block[{nandemo,keisuulst,anyhead,kotaelst,polyans,hensuu}, hensuu=Variables[alg,z]; keisuulst=CoefficientList[z,hensuu]; kotaelst=keisuulst /.anyhead_[nandemo_]->nandemo; polyans=ChToDecimal[Reverse[kotaelst],Characteristic[alg]]; Return[ alg[polyans]]; ]; RegularRepresentation[alg_,z_List] := Block[{vecans}, vecans=ChToDecimal[Reverse[z],Characteristic[alg]]; Return[alg[vecans]]; ]; PGCD[field_[x_Integer], field_[y_Integer]]:= field[1] /; x >= 1 && y >= 1 ; PGCD[field_[0], poly_ ]:= Block[{vari}, vari=Variables[poly]; If[ vari === {}, If[ poly === 0 || poly === field[0], Return[0 ], Return[ field[1] ] ]; ]; Return[ Expand[Coefficient[poly,vari,Exponent[poly,vari[[1]] ]]^-1 poly]] ]; PGCD[poly_, field_[0]]:= PGCD[field[0],poly]; PGCD[field_[x_Integer], poly_]:= field[1] /; x >= 1; PGCD[poly_, field_[x_Integer]]:= field[1] /; x >= 1; Unprotect[PolynomialGCD]; PolynomialGCD[poly1_ , poly2_ ] := Block[ {vari,vari2,vari3,coef,field,poly01,poly02}, field = AlgebraName[poly1]; If[MemberQ[AlgebraNames,field], , field=AlgebraName[poly2] ]; vari2= Variables[poly1]; vari3= Variables[poly2]; If[ Length[vari2]==0 || Length[vari3]==0 , poly01=poly1; poly02=poly2; If[poly1===0 || poly1===1, poly01=field[poly1] ,]; If[poly2===0 || poly2===1, poly02=field[poly2] ,]; Return[PGCD[poly01,poly02] ] ,] ; If[ ExtensionDegree[field] == 1, Return[ PrimePolynomialGCD[poly1,poly2] ]; , If[ Length[vari2] >= 2, Print[poly1," is a multivariate polynomial."]; Return[] ,]; If[ Length[vari3] >= 2, Print[poly2," is a multivariate polynomial."]; Return[] ,]; If[vari2==={}, vari = vari3[[1]], vari=vari2[[1]] ]; Return[ PolynomialGCD[poly1,poly2,vari] ]; ]; ] /; MemberQ[AlgebraNames,AlgebraName[poly1]] || MemberQ[AlgebraNames,AlgebraName[poly2]] ; (* GCD of Polynomials over prime field *) PrimePolynomialGCD[poly1_,poly2_]:= Block[{ po1,po2,a,field,pgcd,vari,coef,vari1,varis, V={V1,V2,V3,V4,V5,V6,V7,V8,V9} ,i}, field = AlgebraName[poly1]; varis = Union[ Variables[field,poly1],Variables[field,poly2] ]; po1= poly1; po2=poly2; For[ i=1, i<= Length[varis], i++, po1 = po1 /. varis[[i]] -> V[[i]]; po2 = po2 /. varis[[i]] -> V[[i]]; ]; po1 = po1 /. { field[a_Integer]->a } ; po2 = po2 /. { field[a_Integer]->a } ; pgcd = PolynomialGCD[po1,po2,Modulus->Order[field]] (* /.{a_Integer -> field[a]} *) /.{Times[a_Integer,b__]->Times[field[a],b]} /.{Plus[a_Integer,b__]->Plus[field[a],b] } ; If[ IntegerQ[pgcd] , Return[ field[1] ], ]; For[ i=1, i<= Length[varis], i++, pgcd = pgcd /.V[[i]] -> varis[[i]] ; ]; pgcd = pgcd /. {Plus[a_Integer, b_] -> field[a] b } ; If[ Length[varis] == 1, vari1= varis[[1]]; coef = Coefficient[pgcd, vari1^Exponent[pgcd,vari1]]; If[ coef == 1, Return[pgcd ] , Return[Expand[pgcd / coef] ] ]; , Return[pgcd] ]; ]; (* GCD of Polynomials over extension field *) PolynomialGCD[poly1_,poly2_,vari_Symbol] := Block[{xpoly,ypoly,wpoly,coef,poly01,poly02} , field = AlgebraName[poly1]; If[ Exponent[poly1,vari]==0 || Exponent[poly2,vari]==0 , poly01=poly1; poly02=poly2; If[poly1===0 || poly1===1, poly01=field[poly1] ,]; If[poly2===0 || poly2===1, poly02=field[poly2] ,]; Return[PGCD[poly01,poly02] ] ; ,]; xpoly = poly1; ypoly = poly2; While[ (ypoly =!= 0) && (ypoly =!= field[0]) , wpoly = xpoly; xpoly = ypoly; ypoly = PolynomialRemainder[wpoly, ypoly, vari]; ]; If[ Variables[field, xpoly] === {}, Return[field[1]],]; coef = Coefficient[xpoly, vari^Exponent[xpoly,vari]]; If[ coef == 0 || coef == 1 , Return[xpoly ] , Return[Expand[xpoly / coef] ] ]; ] /; MemberQ[AlgebraNames,AlgebraName[vari]]; Protect[PolynomialGCD]; EPGCD[field_[x_Integer], field_[y_Integer]]:= {field[1] ,{field[x]^-1 ,0}} /; x >= 1 && y >= 1 ; EPGCD[field_[0], poly_ ]:= Block[{vari,lc}, vari=Variables[poly]; If[ vari === {}, If[ poly === 0 || poly === field[0], Return[ {0,{0,0}} ], Return[ {field[1],{0,poly^-1}} ] ]; ]; lc = Coefficient[poly,vari,Exponent[poly,vari[[1]] ]]; Return[{ Expand[lc^-1 poly],{ 0, lc}} ]; ]; EPGCD[poly_, field_[0]]:= Block[{g}, g = EPGCD[field[0],poly]; Return[ {g[[1]],{g[[2,2]], g[[2,1]]}}]; ]; EPGCD[field_[x_Integer], poly_]:= {field[1],{ field[x]^-1, 0}}/; x >= 1; EPGCD[poly_, field_[x_Integer]]:= {field[1],{0, field[x]^-1}} /; x >= 1; PolynomialExtendedGCD[0,0] := {0,{0,0}}; PolynomialExtendedGCD[1,1] := {1,{1,0}}; PolynomialExtendedGCD[p_,q_] := Block[{po,ly,var,quo,stockpo,stockgg,stockff,coef,i, g0=1,g1=0,f0=0,f1=1,field,switch=False,px,gx,fx}, field=ExpAlgebraName[p]; If[MemberQ[AlgebraNames,field], , field=AlgebraName[q]]; vari2= Variables[field,p]; vari3= Variables[field,q]; If[ Length[vari2]==0 || Length[vari3]==0 , If[p===0 ,Return[EPGCD[field[0],q]] ,]; If[p===1 ,Return[EPGCD[field[1],q]] ,]; If[q===0, Return[EPGCD[p,field[0]]] ,]; If[q===1, Return[EPGCD[p,field[1]]] ,]; Return[EPGCD[p,q] ] ,] ; If[ Variables[field, p] === {}, Return[ {field[1], {p^-1, 0}}] , var = Variables[field,p][[1]]; ]; If[Exponent[p,var] < Exponent[q,var], switch= True; po = q; ly = p ; , po = p; ly = q ; ]; While[ly =!= 0 && ly =!= field[0], quo=PolynomialQuotient[po,ly,var]; stockpo=po; po=ly; ly= Expand[stockpo-po*quo]; stockgg=g0; g0=g1; g1= Expand[stockgg-g0*quo]; ]; px = po; If[ switch, gx = PolynomialQuotient[Expand[(po - g0 q )],p,var]; fx = g0; , gx = g0 ; fx = PolynomialQuotient[Expand[(po - g0 p )],q,var]; ]; If[ Variables[field, px] === {}, Return[{Expand[px/px] ,{ Expand[gx/px],Expand[fx/px]}}],]; coef = Coefficient[po, var^Exponent[px,var]]; If[ coef == 0 || coef == 1 , Return[{px , {gx, fx} }] , Return[{ Expand[px/coef],{Expand[gx/coef],Expand[fx/coef]}}] ] ] ; PthRoot[ al_[x_Integer] ] := Block[ {expx,pinv,y }, If[ExtensionDegree[al] < 2, Return[al[x]]; , If[ListQ[GFExponents[al] ], expx = GFExponents[al][[x+1]] ; pinv = PowerMod[ Characteristic[al], -1, Order[al]-1]; y = GFElements[al][[ Mod[ expx * pinv , Order[al]-1 ]+2 ]]; Return[al[y]]; , Print["PthRoot: can not compute in this field"]; ]; ]; ]; ShiftRegister[l_List,pol_List]:= Block[{l1,ll}, ll = RotateRight[l]; l1 = ll[[1]]; ll[[1]] = 0; If[ l1 == 0 , Return[ll] , Return[ll + l1 * pol] ]; ]; ShiftRegister[l_List,pol_List,k_Integer]:= Block[{i,lm}, lm = l; For[i=1,i<=k,i++, lm = ShiftRegister[lm,pol]; ]; Return[lm] ]; Polynomialize[lst_List,v_Symbol] := Block[ {nlst,vari,i}, nlst = Length[lst]; vari = Table[v^i,{i,0,nlst-1}]; Return[ Apply[Plus,lst*vari] ]; ]; PrimitiveQ[x_]:= Block[ {q,d,i}, q = Order[AlgebraName[x]]; d = FactorInteger[q - 1]; For[ i= 1, i<= Length[d], i++, If[ x^((q-1)/d[[i,1]]) == 1, Return[False]; ,]; ]; Return[True]; ]; PrimitiveQ[x_]:= False /; x == 0; Unprotect[Order]; Order[alname_[x_Integer]]:= Block[{ele,k,q}, Cycle[ele_,k_Integer]:= Block[ {kd,d,i}, d = FactorInteger[k]; If[k == d[[1,1]], Return[k],]; For[ i= 1, i<= Length[d], i++, kd=k/d[[i,1]]; If[ ele^kd == 1, Return[Cycle[ele,kd]]; ,]; ]; Return[k]; ] ; q = Order[alname]; Return[Cycle[alname[x],q-1]]; ] /; x >= 2 ; Order[alname_[0]]:= Return[Print["Order of ",alname[0], " is undefined."]]; Order[alname_[1]]:= Return[1]; MinimalPolynomial[a_,vari_] := Block[ { p,gfname,bb,ii,Mp, vv,exdeg}, If[ a == 0, Return[ vari ] , ]; gfname= AlgebraName[a]; p = Characteristic[gfname ]; exdeg = ExtensionDegree[gfname]; DeclareAlgebraicVariables[gfname,vv]; bb = a; Mp = vv - a ; For[ii=1, ii < exdeg, ii++, bb = bb^p; If[ bb === a, Break[], Mp = Expand[ Mp (vv - bb)]; ]; ]; Return[Mp /. vv -> vari /. gfname->BaseField[gfname] ]; ]; (* ---------------- Miscellaneous functions ---------------- *) (* SqrtMod was copied from NumberTheory Package *) SetAttributes[PowerMod, Listable]; SqrtMod[d_Integer, n_Integer]:= Mod[Sqrt[d], n] /;IntegerQ[Sqrt[d]]; SqrtMod[d_Integer, q_Integer] := Block[{e, p = q, q2,z,n,v,w,k,t,a,cnt=0}, e = 1; qq = (p-1)/2; While[EvenQ[qq], e++; qq /= 2]; If[ e == 1, z = -1, n = 2; While[JacobiSymbol[n,p] != -1, n++]; z = PowerMod[n,qq,p] ]; v = PowerMod[d,(qq+1)/2,p]; w = Mod[PowerMod[d,-1, p] Mod[ v v ,p], p]; While[w != 1, cnt++; k = 1; t = Mod[w w,p]; While[t != 1, k++; t = Mod[t t,p]]; a = PowerMod[z,2^(e-k-1),p]; e = k; v = Mod[v a, p]; z = Mod[a a,p]; w = Mod[w z,p]; ]; Return[v] ] /;OddQ[q] && JacobiSymbol[d,q] == 1 && PrimeQ[q]; Protect[ AlgebraName ,GFElements ,AlgebraNames ,GFExponents ,BaseField ,GFVariables ,Characteristic ,IrreduciblePolynomial ,ChToDecimal ,MakeGaloisField ,CleanUp ,NonZero ,ClearAlgebra ,NonZeroQ ,ClearVariables ,NonZeroVariables ,DeclareAlgebraicVariables ,PolynomialEGCD ,DeclareGaloisField ,PolynomialExtendedGCD ,DeclareIndeterminates ,Polynomialize ,DeclareVariables ,PolynomialRepresentation ,ExpAlgebraName ,PthRoot ,ExponentRepresentation ,RegularRepresentation ,ExtensionDegree ,ShiftRegister ,GFAlgebraicVariables ,SqrtMod ,GFAllAlgebraicVariables ,VectorRepresentation ,GFAllVariables,Order ,Zero ,Order ,PrimitiveQ ,ZeroQ ,OneQ ,MinimalPolynomial ]; Print["GaloisField.m was loaded."]; End[ ] ; EndPackage[];