Galois Field Package
Manual

Ryoh Fuji-Hara
University of Tsukuba

Abstract

When we implement an algebraic system like a group, a ring or a finite field within an existing symbolic computational language, then there are three possible approaches:
(1) define new operators:  for example; if we define an operator  %+% for addition on a finite field, then we could operate in  the following fashion:  2 %+% 4 .
(2) change mode:  for example; if we write ChangeAlgebra[GF,7], then every computation is done over GF(7) until  we change to some other algebra.
(3) use the same operations within the existing system (i.e. +,-,*,/ ):  for this we have to identify constants and variables to be in a certain algebra.  In this method a lot of original functions of the system become available to the new algebra.
     Due to the fact Mathematica is an object based it facilitates the adaptation of the third method cited above. Thus, the package allows us to use many functions of Mathematica over finite fields without any modification, i.e.;  solving linear equations, inverses, determinants, derivations, resultants, etc..
    
   

1. Finite Fields

A finite field ( or Galois field ) is, generally speaking, a finite set having  algebraic properties like Quotient, Real or Complex  except topological and ordering  properties.  We define a finite field mathematically as follows:
     Let K be a finite set.  + and * are binary operations defined on K.  If the following properties are satisfied then the an algebraic system (K,+,*) is called a finite field (or Galois filed).

1. + and * are closed on K,
2. for any elements a and b of K, a+b=b+a and a*b=b*a,
3. for any elements a, b and c of K, (a+b)+c=a+(b+c) and (a*b)*c=a*(b*c),
4. for any elements a, b and c of K, a*(b+c)=a*b+a*c,
5. there exist unique an additive identity 0 and a multiplicative identity 1,
6. for any element a of K, there exists a unique additive inverse -a.  And for any nonzero  
   element b of K, there exits a unique multiplicative inverse b-1.

If there are q elements in K, we write GF(q) for the finite field (K,+,*). Then the number of elements in K is called the order of the field.

Theorem 1.  There exists a finite field of order q if and only if q is a prime or prime power.

     If  q is a prime number, then it is easy to construct a finite field of order q. Let K be {0,1, 2,..., p-1}.   If  we consider the addition and the multiplication on K to compute under the modulo p,  +(mod p) and *(mod p) , then this algebraic system (K, +(mod p) , *(mod p)) is the finite field GF(p), and it is called a prime field. If a subset S of the elements of a finite field F satisfies the above axioms with the same operators of F, then  S is called  a subfield.

Theorem 2.  Let F be a finite field of order qn , p a prime number.  There exists a subfield of order pm if and only if m divides n.

      Consider a finite field with the order of a prime power number.  Let f(x)=x3+x+1 be a polynomial over GF(2) which is unfactorable. Such a polynomial is called an irreducible polynomial.  Using the modulo x3+x+1, we can reduce x0 , x1 , x2 , ...  to polynomials with degree less than 3.

                        Power                  Polynomial            Vector           Regular
                        
                          	0                              	0                    	(000)                	0
                         	x0=1                         	1                    	(100)                	1
                         	x1                          	   x                    	(010)                	2
                         	x2             	                x2                  	(001)                	4
                         	x3                           	1+x                  	(110)                	3
                         	x4           	                x+x2                	(011)                	6
                         	x5                       	1+x+x2                	(111)                	7
                         	x6                       	1+    x2     	           (101)                	5

The first and second columns are called power and polynomial representations, respectively.   The third column contais the triples of coefficients of the polynomial representations, called the vector representation.  The last column, called regular representation, contains the integer representations of vectors which are regarded as binary numbers.  The set of the above polynomials in the second column are closed under addition and multiplication with the modulo f(x), and these operations on the set satisfy the axioms of finite field.  This finite field is said to be an extension field of degree 3 of GF(2) and write GF(23). Then the field GF(2) is called the base filed of GF(23).  Note that it is not sufficient to generate all elements of extension field 0, x0, x1,... are generated by an irreducible polynomial. If an irreducible polynomial generates all elements in the above way then it is called a primitive irreducible polynomial.

Theorem 3.  For any prime or prime power q and any positive integer n,  there exist a primitive irreducible polynomial of degree n over GF(q).

        We have now two finite fields F1 and F2 of the same order q.  If there is a 1-1 mapping 
g: F1 -> F2  such that g(x) + g(y) = g(x + y) , g(x)g(y) = g(xy),  then the fields F1 and F2 are said to be isomorphic. If order of F1 is less than the order of  F2  then  we say that F1 is homomorphic to F2 .

Theorem 4.   Two finite fields of the same order are isomorphic.

      The following are important properties of finite fields:

Theorem 5.  For any element c of GF(q),  cq=c.

Theorem 6.  For any nonzero element d of GF(q), dq-1=1.

      The smallest positive integer n such that

in GF(q) is called the characteristic of the field GF(q). The characteristic is a prime number for every finite field.

Theorem 7.  (x+y)p = xp + yp over a finite field with characteristic p.

2. Installation and Start-up

The floppy disk "Galois Field Package" contains a folder named "Galois Field".  The folder contains the following files:
     
           	GaloisField.m
           	GaloisFieldFactor.m
           	GF4
           	GF8
           	GF16
 	             .
          	    .

Installation for Macintosh

First, copy the folder into the Mathematica folder. Then you have to add a line in the  Mathematica file "init.m" which is in the folder "Packages". You have to add the following line in the file "init.m" :
    
$Path = Join[ {":Galois Field"}, $Path ];

Installation for UNIX

Copy the folder under your working directory.  Note that UNIX does not allow a file/directory name including a blank. Therefore you have to use the name "GaloisField" without blanks. Next you have to eddit init.m. If you do not have the file "init.m" in your working directory, you can copy it from directory "StartUp" under Mathematica's home directory.  Then add the following line in the file "init.m":
  
  $Path = Join[ {"./GaloisField"}, $Path ];
  
   Note that the folder name "GaloisField" is not fixed in the Galois field Package, so you can use any name you ike.

Start Up

Now you can start Mathematica.  In a Mathematica session, if you type

<<GaloisField.m

Then the Galois Field Package is ready to use.  If you get the following message:

Mathematica can't find the file "GaloisField.m".  
Please locate this file, or click "Cancel" if you don't want to open it.

You should correct the setting of $Path in the file "init.m".

3. Algebra Names and Constants

When we declare a finite field, we name the field using the following rules:  
    
·    The first character must be a letter.
·    It is not allowed to use a symbol (a string) which is used in Mathematica.
·    You will get a warning message if you use a name with the length of  one character .

It is called algebra name.   We can use different algebra names for finite fields with the same order.   Every element of a finite field, that is, a constant,  has the following form:

                                     algebra name[ integer ]

The integer in the form must be a regular representation of the finite field. For example, suppose we now have an algebra name K5 for GF(5), then we can write the following expressions:

K5[2] + K5[4]

K5[2]^3

K5[2] * K5[3] + K5[1]

K5[3]^-1

Sqrt[K5[4]]

In this case, the order of K5 is a prime, 5, therefore the integers that appear in the brackets [ ] are 0,1,..., or 4.   In the case of an extension field GF(qn),  the regular representation is used for the integers in the brackets.  The regular representation has some advantages as listed below:

·    0 is the additive identity and 1 is the multiplicative identity for any field.
·    In a finite field GF(qn) with the base field GF(q),  0,1,,..., q-1 are always the elements 
     of its base field.
·    In a finite field with characteristic p,  {0, 1,..., p-1} is always a subfield (prime field).
·    Between an extension field of degree m and a extension field of degree n over GF(q),  
     (m <n), there is the natural correspondence,  σ : i -> i  , of homomorphism with 
     respect to the additions.

      Let K9 be the algebra name of GF(32). Then, for instance,  K9[3] , K9[4],  K9[5], K9[6]  are representations of (0,1),  (1,1),  (2,1),  (0,2),  respectively.

K9[4] + K9[5]

K9[6]^-1

K9[3]^0

K9[0] is the additive identity and K9[1] is the multiplicative identity of  K9.  K[0], K9[1], K[2]  are the elements of the base field GF(3) of K9.   Algebra names are defined as Listable in Mathematica,  therefore, it is easy to define a vector:

K9[{1,3,5}]

You can input K9[0] as

K9[0] K9[4]

however, if its result is zero then the output form is 0 instead of K9[0].  The reason is that some Mathematica functions, like Nullspace, Solve,... ,   may not understand K9[0] as 0. Therefore, when a result is zero in a Galois field , then  this package always returns 0.

4. Types of Finite Fields

There are four  types of declarations for finite fields in this package depending on different constructions of finite fields.
     
I	     Prime fields
II     Extension fields over a prime base field.  (needs a Galois field object)
III	  Extension fields over a declared base field. (needs a Galois field object)
IV	  Extension fields over a declared base field. (no objects needed )

When we declare a finite field of type II or III,  then there must exit the object  of the finite field must exist as a file; it is called a Galois field object.  A Galois field object can be created in precomputation and saved as a file.

Type I

After loading the Galois Field Package by inputting  <<GaloisField.m, we declare a finite field with the function DeclareGaloisField.

DeclareGaloisField[K5,5]

This example declares a prime field of order 5, GF(5). Then we can use the algebra name K5 and constants K5[i] for i=0,1,...,4.

K5[3] + K5[4]

Type II and III

When you declare a type II or III finite field,  just use the function  DeclareGaloisField

DeclareGaloisField[GF16]

If the object  GF16 does not exist,  you get the following message:

   Galois field object, GF16, does not exist.
   
Then you can make a type II object with the following function:

MakeGaloisField[GF16,2,4,{1,1,0,0,1}]

The first argument is the name of the object (also used as algebra name), the second is the order of the base field (must be a prime number), the third is the extension degree and the fourth argument is the coefficient list of a primitive irreducible polynomial over the base field.  The function saves the object as a file with the name of the first argument.
When you make a type III object,  the second argument of MakeGaloisField must be an algebra name of the base field.

MakeGaloisField[F16,GF4,2,{2,2,1}]

Of course, the base field must be declared before executing this function.  The base field for type III  does not have to be a prime field.

Type IV

Type IV Galois fields do not require objects for them.  If a base field has been declared, then you can declare a type IV Galois field directly by the function DeclareGaloisField.

DeclareGaloisField[K16,GF4,2,{2,2,1}]

Since the fields of this type do not have any table for computations,  in each computation  on type IV finite fields, elements are reformed to polynomials over the base field and compute under the modulo of the irreducible polynomial.  Therefore the irreducible polynomial does not have to be a primitive.  So, if you use a reducible polynomial instead of an irreducible polynomial, you can declare a polynomial ring.
     Type IV Galois fields are not recommended for fields of an order less than 1000, because the computations are very slow.

5. Variables on Galois fields

The Galois Field Package has two kinds of variables over finite fields.  One is a variable which represents an element of a field.  When we see in a mathematics book "for an element x of the field K" , the symbol x represents a constant of K.  This variable  works like an element of K and may be substituted by a constant later.  The second kind of variable is called an indeterminate or an algebraic variable. The algebraic variable can never be substituted by a constant and dose not work like an element.  Theorem 5 works on a variable which represents an element but not on an algebraic variable. 
When we declare variables which represent elements of the finite field K9:

DeclareVariables[K9,x,y]

Since  K9 is a finite field of order 9,  theorem 5 works like

x^9

x^-10

From theorem 5,  x9=x in GF(9).  Exponents of variable x in outputs can never be larger than 8 ( generally "order" - 1).
Mathematica does not print in the form  " x0 ".  Therefore, the Galois Field Package prints  with the form " xZero ".  The symbol  Zero  exactly works as the numeric number 0.

x^0

% /. x-> K9[5]

The theorem 6 says that if x is an nonzero element of K9 then x8=1.  The Galois Field Package have a declaration function for nonzero variable.

NonZero[x]

x^{0,1,2,3,4,5,6,7,8,9,10}

You can compare with a ordinal variable y of K9.

y^{0,1,2,3,4,5,6,7,8,9,10}

{x , y }^16

Note that 0-th power of 0 is indeterminate.

K9[0]^0

Nonzero variables can also be declared by the NonZero option in the function DeclareVariables.

DeclareVariables[K9,x, NonZero -> True]

Inverse[{{ x,1},{0,x}}]

Next, when we declare an algebraic variable, we use the function DeclareAlgebraicVariables or DeclareIndeterminates.

DeclareAlgebraicVariables[K9,X,Y]

Using the algebraic variable, we can define a polynomial ring GF(9)[X].  Since algebraic variables are not elements of a finite filed,  theorem 5 and 6 have no effect on X and Y.

X^9

We define the 0-th power of an algebraic variable to be 1.

X^0

Since X, Y are indeterminate, you can not substitute a constant to these variables.

X = K9[2]

6. Mixed operations with integers or constants of the base field.

Let GF9 be a Galois field of order 9 with base field GF3.  Regular representations of GF3 , 0, 1, 2  correspond to those of GF9. So

GF3[2] + GF9[7]

and

GF9[2] + GF9[7]

have the same results.  If you consider that GF9 is the 3-dimensional vector space over GF3,  then  addition of vectors and scalar product work  as  a vector space without any  modification.
    The Galois Field Package allows  addition and multiplication with integers.  An integer k in a mixed expression is recognized as  Sum[GF9[1],{i,k}], when we compute in GF9.  Hence k is translated to the regular representation  k (mod p), where p is the characteristic of the field.

3 + GF9[4]

4 GF9[3]

DeclareVariables[GF9,x]

5 x

This  feature guarantees  that theorem 7 works for both variables and algebraic variables.

Expand[ (x+y)^3]

( x, y are variables of GF9 )

Expand[ (X + Y)^3]

(X, Y are algebraic variables of GF9)

Expand[ (u + v)^3 ]

( u, v are just symbols in Mathematica)

And also Derivation over a finite field works.

DeclareVariables[GF9,a,b,c]

DeclareAlgebraicVariables[GF9,X]

D[a X^2 + b X + c, X]

7. Making Galois field objects

When you declare a Galois field of type II or type III, there must exist the Galois field object for the field must exist. Once you make an object, you can just declare the Galois field with the algebra name.

For a type II field:
MakeGaloisField[ al,  ord, exd,  ipp ]
        al:     algebra name
        ord:   order of base field
        exd:   extension degree
        ipp:    a coefficent list of a primitive irreducible polynomial

A type II Galois field object is made with the following function:

MakeGaloisField[K16,2,4,{1,1,0,0,1}]

Galois field object K16 was saved.

This function makes a Galois field object with algebra name K16 = GF(24) over the base field GF(2) using a primitive irreducible polynomial 1+x+x4.
If we try to make an object which already exists, then we will get the following message:

     Galois field object K16 already exists.
     K16 can not be made.

For a type III field:
MakeGaloisField[ al,  bal, exd,  ipp ]
      al:    algebra name
      bal:   algebra name of a base field
      exd:  extension degree
      ipp:   a coefficent list of a primitive irreducible polynomial

A type III Galois field object is made with the same function but the second argument is different. The second argument of Type III MakeGaloisField must be an algebra name of the base field.  The base field  must have been declared when you make the type III Galois field. If the base field has not been declared,  you will get the following message:

MakeGaloisField[bb,base,2,{2,2,1}]

base has not been declared.
     bb can not be made.

Note that if the algebra name which you want to make is already declared, you can not make a Galois field object with the name.

MakeGaloisField[bb,base,2,{2,2,1}]

bb has been declared already.
     bb can not be made.

So, if the conditions

1)   the base field has been declared,
2)   the algebra name of the object (the first argument) is not declared

are satisfied , then you can make a Galois field object.

MakeGaloisField[bb,base,2,{2,2,1}]

Galois field object bb was saved.

8. Declaration of Galois fields

When we have finished setting up the environments to use a Galois field package mentioned in the section 2, we next have to declare a Galois field using the function DeclareGaloisField with an algebra name and some parameters of the field.

For a prime field:
DeclareGaloisField[ algebra name,  order ]

The order must be a prime number p for declaring a prime field.  This  declares a type I Galois field and calculations of constants are always done under the  modulus p.

DeclareGaloisField[Z5,5]

Z5[3]^3 + Z5[4]^2 + Z5[2]^(-2)

Sqrt[Z5[4]]

We can also declare an algebra with an order of a non prime number using this function, We then can have a modular ring Z/(m).  Addition and multiplication in a modular ring work correctly but inverses are not guaranteed.

DeclareGaloisField[Z6,6]

Z6[2] + Z6[3]^3

Z6[2]^-1

In Z/(6), the inverse of 2 does not exist.  We should not compute  inverses in the algebra.

For an extension field (type II or III) :
DeclareGaloisField[ algebra name ]

This is for declaring type II and III Galois fields.  If a Galois field object of the algebra name exists, then this function loads the file of the object.  If there does not exist the object then the Galois field Package gives the following message:

DeclareGaloisField[ abc ]

When the object exists you will get the following message

DeclareGaloisField[GF16]

Then it is ready to compute over GF(16), for example,

GF16[13]^4 + GF16[14] + GF16[6]

Sqrt[GF16[12]]

For an extension field (type IV) :
DeclareGaloisField[ al,  bal, exd,  ipp  ]
      al :    algebra name
      bal :   algebra name of a base field: 
      exp :  extension degree
      ipp :   a coefficent list of an irreducible polynomial

This declaration gives an extension field without a Galois field object.  However, we need a base field to be declared before we execute this function.  This type of Galois field does not have any table to calculate, so this is not recommended for small Galois fields.
Note: the irreducible polynomial does not have to be primitive.  Furthermore, if we use a reducible polynomial then we will have a polynomial ring.

FX = CoefficientList[ 1+ x^7 + x^127, x]

DeclareGaloisField[FF, GF2,127, FX ]

FF[132] + FF[321]

DeclareGaloisField[ ]

The function DeclareGaloisField without arguments gives the list of algebra names which are currently declared.

DeclareGaloisField[]

ClearAlgebra[ al1, al2, al3,...]
    al1, al2, al3 : algebra name

When we declare a finite field,  the Galois field package defines  some symbols and functions in the Global context.   For example,

DeclareGaloisField[GF2,2]

?Global`*

AdditionGF2  ConGF2Q  GF2    NZVGF2Q     Quit    VGF2Q
     AlVGF2Q      Exit     MultipleGF2        PowerGF2

If you want to remove those,   you can do without using the Remove function for each.

ClearAlgebra[GF2]

?Global`*

Exit Quit

If you do not want to remove variables which are declared by DeclareVariables or DeclareAlgebraicVariables,   just use the option RemoveVariables -> False .

ClearAlgebra[GF2, RemoveVariables->False]

But the attributes of the variables (  algebra names ) are erased.

9. Attributes of Galois fields

A declared Galois field has following six attributes including the algebra name:
              	algebra name
              	characteristic
              	order
              	extension degree
              	irreducible polynomial
              	base field
The last three of them are not defined for prime fields.

Characteristic[ algebra name ]

If  we declare a Galois field as follows

DeclareGaloisField[GF16]

Then we have

Characteristic[GF16]

Order[ algebra name ]

gives the order of the Galois field.

Order[GF16]

ExtensionDegree[ algebra name ]

returns the extension degree over the base field. When the Galois field is a prime field, this function is unavailable.

ExtensionDegree[GF16]

IrreduciblePolynomial[ algebra name ]

returns the list of an irreducible polynomial whih is used for constructing the Galois field of the algebra name. When the Galois field is a prime field, this function is unavailable.

IrreduciblePolynomial[GF16]

BaseField[ algebra name ]

returns the algebra name of the base field. When the Galois field is a prime field, this function is unavailable.

BaseField[GF16]

10. Variables on Galois fields

There are two kinds of variables in the Galois field package.  The first is a variable which represent an element of a Galois field, the second is  an indeterminate. The first is declared by the function DeclareVariables and the second is declared by DeclareAlgebraicVariables.

DeclareVariables[ algebra name, Var1, Var2, ... ]
DeclareVariables[ algebra name ]
DeclareVariables[ ]

If  a Galois field of the algebra name K is declared,  DeclareVariables[K,  Var1,  Var2] defines variables Var1 , Var2  as symbolic elements on the Galois field K.

DeclareVariables[Z5,x,y]

Now,  x and y are variables on Z5,  and we have the following results

3 x^4 * 4 x^3

Expand[(x + y)^5]

Solve[x^2 + Z5[1]== 0 ,x]

DeclareVariables[ algebra name ] returns the list of the variables which are currently declared with respect to the algebra name.
DeclareVariables[ ] returns the list of all variables declared in this session of the Galois field package.

DeclareVariables[Z5]

DeclareVariables[GF9]

DeclareVariables[]

NonZero[ Var1, Var2,...]
DeclareVariables[ algebra name, Var1, Var2,..., NonZero->False]
NonZeroQ[ Var ]
NonZero[ ]

When  x and y are declared as variables on a Galois field, the function NonZero[x,y] declares  x and y to be nonzero variables.   NonZero[] returns the list of all variables which are currently declared as nonzero variables.  NonZeroQ[Var] returns True if Var is a nonzero variable, otherwise it returns False.

DeclareVariables[K5, x, y]

NonZero[ x ]

NonZeroQ[x]

NonZero[]

The difference between ordinal variables and nonzero variables is shown below

{x , y}^0

{x , y }^4

The zero-th  power of a nonzero variable returns 1, otherwise it returns in the form yZero. The (order - 1)-th power  of nonzero variable returns 1.

DeclareVariables[K5, x, y]

NonZero[ x ,y ]

can be written with the following one function

DeclareVariables[K5, x, y, NonZero -> True]

Default of the NonZero  option is False.

DeclareAlgebraicVariables[ algebra name, Var1, Var2, ... ]
DeclareAlgebraicVariables[ algebra name ]
DeclareAlgebraicVariables[ ]

This function declares algebraic variables (indeterminacies).  Galois field of the algebra name must be declared before executing this function.

DeclareAlgebraicVariables[K5,a,b]

then a and b are algebraic variables over K5=GF(5).   Since an algebraic variable does not represent an element of GF(5), the theorems 5 and 6 do not work on it,  i.e. a^5 is not equal to a ,  a^4 is not equal to 1.  However we define the 0-th power of an algebraic variable to be equal to 1.

3 a^4 * 4 a^3

a^0

Let K2=GF(2). We declare x, y as just variables  and c, d as algebraic variables on K2, respectively. And m, n are just symbols which are not declared in the Galois field package.  Then we can see the difference of those symboles in the following:

DeclareVariables[K2,x,y]

Expand[(x+y)^2]

DeclareAlgebraicVariables[K2,c,d]

Expand[(c+d)^2]

Expand[(m+n)^2]

We can use the function name DeclareIndeterminates instead of DeclareAlgebraicVariables .
DeclareAlgebraicVariables[ algebra name ] returns he list of algebraic variables declared on the algebra name. DeclareAlgebraicVariables[] returns the list of all  algebraic variables declared in this Galois field package session.

DeclareAlgebraicVariables[K5]

DeclareAlgebraicVariables[]

All algebraic variables are protected in Mathematica. Hence, you can not substitute a value to the algebraic variables.

a = K5[1]

ClearVariables[ Var1, Var2,... ]

The function ClearVariables removes variables or algebraic variables in the arguments, including functions and attributes defined with respect to the variable names.  It is recommended to use this function insted of the Mathematica functions Clear and Remove.

AlgebraName[ expression ]

This function returns the name of a Galois field on which the expression ( may be a variable ) is declared.

AlgebraName[x]

AlgebraName[ (x + 1)^2 ]

AlgebraName[{ x, y}]

11. Utilities

ExponentRepresentation[ Galois field constant, symbol ]

This function converts from the regular representation to an exponent representation with the symbol as a primitive element.

ExponentRepresentation[GF16[12],a]

Note: This function does not work for type I and type IV Galois fields.

PolynomialRepresentation[ Galois field constant, symbol ]

converts a Galois field constant from regular representation to its polynomial representation on the symbol.

PolynomialRepresentation[GF16[12],x]

we can put a vector representation of the Galois field constant  in the first argument.

PolynomialRepresentation[{1,0,1},x]

VectorRepresentation[ Galois field constant ]

converts a Galois field constant from regular representation to its vector representation.

VectorRepresentation[GF16[12]]

RegularRepresentation[ algebra name, Galois field constant ]

RegularRepresentation  converts from a Galois field constant ( of any representation) to regular form.

RegularRepresentation[GF16,x^6]

RegularRepresentation[GF16,x^3 + x^2]

RegularRepresentation[GF16,{0,0,1,1}]

PolynomialGCD[ polynomial1, polynomial2 ]
PolynomialGCD[ polynomial1, polynomial2, algebraic variable ]

PolynomialGCD is modified from Mathematica's original function to work on Galois fields. The function returns the greatest common divisor of the two polynomials over a finite field.  The result is always a monic polynomial.

PolynomialGCD[x^5+GF9[1], x^3+GF9[1]]

PolynomialGCD with three arguments is newly made for the Galois field package. This PolynomialGCD works for multivariate polynomials.

PolynomialGCD[x^5+GF9[3] y ,x^3+y , x]

PolynomialExtendedGCD[ polynomial1, polynomial2 ]

PolynomialExtendedGCD returns the greatest common divisor d(x) of two polynomials in the arguments  f1(x)  and f2(x),  and also returns a(x) and b(x) such that
                         a(x) f1(x)  +  b(x) f2(x)  = d(x).
The output  form is { d(x) , { a(x),  b(x) } }.  The arguments polynomial1 and  polynomial2  must be univariate polynomials and the  variable of the polynomials must be an algebraic variable.

DeclareAlgebraicVariables[GF9,x]

PolynomialExtendedGCD[x^3-1, x^2-1]

Expand[(x^3-1) + ( x*GF9[2]) (x^2-1)]

ShiftRegister[ list1, list2 ]
ShiftRegister[ list1, list2, integer ]

This process is called a feedback shift register. Let list1 =  {a1, a2, ... ,an} and  list2 = {b1, b2, ...,bn }, the output is  {0, a1, ..., an-1} + an * {b1, b2, ..., bn}.  ShiftRegister[list1, list2,k] executes ShiftRegister[list1, list2] k times.

ShiftRegister[GF2[{1,0,1}], GF2[{0,1,1}]]

PthRoot[ Galois field constant ]

returns the p-th root of the Galois field constant ( regular representation ) , where p is the characteristic of the field.  Note: the p-th root of an element x in a prime field is x.

PthRoot[ K5[3] ]

PthRoot[ GF9[5] ]

Note: This function does not work for type IV Galois fields.

Variables[ expression ]
Variables[ algebra name,  expression ]

Mathematica's original function Variables  returns all symbols including Galois field constants.  Therefore the function Variables is modified in the Galois field package. This function in the Galois field package does not returns Galois field constants.

Variables[ X^2 + K5[2] X Y + Y^2 ]

If we use Variables[algebra name, expression], it executes faster than  the function 
Variables[ expression] without the algebra name.

Variables[K5, X^2 + K5[2] X Y + Y^2 ]

Polynomialize[ list ,  variable ]

This function is the inverse process of the function CoefficientList.

Polynomialize[{GF9[1], 0 , GF9[2], 1}, x]

The Sqrt function is also modified for working on the Galois fields.

MinimalPolynomial[ Galois field constant, symbol ]

This function returns a polynomial over the base field which has the constant of the first argument as a  root .  The constant must be an element of an extension field.  The symbol of the second  argument is used for the returned polynomial as the algebraic variable over the base field. The symbol is automatically declared as an algebraic variable over the base field.

MinimalPolynomial[GF9[7],x]

% /. x-> GF9[7]

12. Factor

Factor and FactorList functions are also modified in the Galois field package to work on finite fields.  Since these functions are in the sub-package GaloisFieldFactor.m,  in order to use Factor and FactorList over a finite field, we have to load the package GaloisFieldFactor.m.

<< Factor.m

Galois Field subpackage Factor.m was loaded

Note: The file name Factor.m was changed for the Windows users from the previous name 
          GaloisFieldFactor.m .
Then we can factor a polynomial over a finite field.

DeclareAlgebraicVariables[GF9,Y]

Factor[Y^2 + Y^5 + Y GF9[7] + Y^4 GF9[7] + GF9[8] 
+ Y^3 GF9[8]]

The variable of a polynomial must be an algebraic variable,  never a variable.

FactorList[Y^2 + Y^5 + Y GF9[7] + Y^4 GF9[7] + GF9[8]
+ Y^3 GF9[8]]

13. On Development of Applications

When we make an application program using the Galois field package,  there are some thing to note.  Let us consider an example.  We have the following definition and theorem on finite fields:

Definition.  If an element a of GF(q) satisfies  αi≠ 1 for  all  i = 1,2,..., q-2,  then α  is called a primitive element of GF(q).

Theorem 8.  A non-zero element α of GF(q) is a primitive  element if and only if 
α(q-1)/di≠  1 for all  factors  d1, d2, ...dr  of q-1.

Using Theorem 8,  we show a function to test a constant of a Galois field to be a primitive element.   PrimitiveQ is designed tor return True if the argument is a primitive element, otherwise to return False.

(1) PrimitiveQ[x_]:= 
(2)   Block[ {q,d,i},
(3)    q = Order[AlgebraName[x]];
(4)    d = FactorInteger[q - 1];
(5)    For[ i= 1, i<= Length[d], i++,
(6)      If[ x^((q-1)/d[[i,1]]) == 1,
(7)          Return[False]; 
(8)       ,];
(9)    ];
(10)   Return[True];
(11) ];
(12) PrimitiveQ[x_]:= False /; x == 0;

Look at the lines (6) and (12).  There, the left hand side of == is a symbol for a Galois field constant but the right hand side is just 1.  Only for 0 and 1 ,  == ( Equal function) is modified to test  for a Galois field constant with them.  So we can write the following logical equations:   x == 1 ,  x != 1 ,  x == 0 ,  x != 0  .
However, if the left hand side contains Galois field variables or algebraic variables, then the above equations do not work.  In such case, we have to use === (Same function) like :

      If[ Expr === 1 || Expr === AlgebraName[Expr][1] , ....]

   When we declare an algebra,  for example GF2, then the following symbols are defined in the Global context:

?Global`*

AdditionGF2 ConGF2Q    GF2    NZVGF2Q     Quit        VGF2Q
     AlVGF2Q     Exit       MultipleGF2        PowerGF2

The symbols,

     AdditionGF2 ConGF2Q     GF2         NZVGF2Q     VGF2Q
     AlVGF2Q     MultipleGF2 PowerGF2

are used by the Galois field package.  These symbols are protected and  not cleared unless you execute ClearAlgebra[GF2].

   Next, we consider a program to obtain the order of a finite field element, that is,  to return the minimum integer k such that ak = 1, for a Galois field constant a.

(1) Unprotect[Order];
(2) Order[alname_[x_Integer]]:=
(3)   Block[{},
(4)      Cycle[ele_,k_Integer]:=  Block[ {d,i},
(5)          d = FactorInteger[k];
(6)          If[k == d[[1,1]], Return[k],];
(7)          For[ i= 1, i<= Length[d], i++,
(8)             If[ele^(k/d[[i,1]]) == 1,
(9)                        Return[Cycle[ele,kd]],  ];
(10)          ];
(11)         Return[k];
(12)     ];
(13)     Return[Cycle[alname[x],Order[alname]-1]];
(14)  ] ;
(15) Order[alname_[0]] := Return["Not available"];
(16) Order[alname_[1]] := Return[1];
(17) Protect[Order];

The function name "Order" is already used twice,  one is originally in Mathematica and the other is in the Galois field package ( order of a field ). Since all function names  of Mathematica including functions in the Galois field package are protected, we can not use the symbol "Order' at the left hand side of :=  (Set function).  Therefore we have to release the protection to use such a symbol, see (1). And we have to write the argument explicitly to distinguish it from other Order functions, see (2). Note that the Order function in (13) is the function to obtain the order of a field. This kind of program is a little dangerous, we may break the other Order function's operation. It is not recommended for Mathematica beginners.
Note that those two functions, PrimitiveQ and Order, in this section are contained in the Galois Field Package.

Ryoh Fuji-Hara

Institute of Socio-Economic Planning
University of Tsukuba
Tsukuba, Ibaraki, Japan 305
Phone: 81-298-53-5088  Fax: 81-298-53-5070
E-mail: fujihara@shako.sk.tsukuba.ac.jp

October 10, 1993