6.34.18  Construction of a Galois field: GF

A Galois field is a finite field. A Galois field will have characteristic p for some prime number p, and the order will be pⁿ for some integer n. Any Galois field of order pⁿ will be isomorphic to ℤ/pℤ[X]/I, where I is the ideal generated by an irreducible polynomial P(X) in ℤ/pℤ[X]

The GF command creates Galois fields.

• GF takes two mandatory arguments and one optional argument:
  • p, a prime number.
  • n, an integer greater than 1 (or an irreducible polynomial over ℤ/pℤ[X]).
    If n is an integer, the first two arguments can be combined and entered as a prime power pⁿ.
  • Optionally vars, either the name of a variable or a list of two or three variables. These variables must be symbolic, so you should purge them if necessary.
• GF(p,n ⟨vars⟩) returns a Galois field of characteristic p having pⁿ elements. The output will look like GF(p,P(k),[k,K,g],undef) where:
  • p is the characteristic.
  • P(k) is an irreducible polynomial generating an ideal I in ℤ/pℤ[X], the Galois field being the quotient of ℤ/pℤ[X] by I.
  • k is the name of the polynomial variable.
  • K is the name of the Galois field (which will be given to a free variable).
  • g is a generator of the multiplicative group K^*. You can build elements of the field with polynomials in g.
  If the optional argument vars is given:
  • vars consists of a variable name, then g is that variable name.
  • If vars consists of a pair of variable names, then k will be the first variable and K will be the second variable.
    In this case, there is no generator given and the elements of K must be given by K(P(k)) for a polynomial P(k).
  • If vars consists of three variable names, then k will be the first variable, K will be the second variable and g will be the third variable.

The elements of the field will be 0,g,g²,…,g^pn−2.

Example.
Input:

Output:

The field K has 2⁸=256 elements and g generates the multiplicative group of this field ({1,g,g²,…,g²⁵⁴}).
The elements of this field can be written as polynomials in g or as K(P(k)), where P(k) is a polynomial in k. Input:

or: Input:

or: Output:

indeed g⁸=g⁴+g³+g²+1, so g⁹=g⁵+g⁴+g³+g.

Once a Galois field is created in Xcas, you can use elements of the field to create polynomials and matrices, and use the usual operators on them, such as +, -, *, /, ^, inv, sqrt, quo, rem, quorem, diff, factor, gcd, egcd, etc.

Examples.

• Compute the inverse of a matrix in a Galois field:
  Input:
  GF(3,5,b):; A:= [[1,b],[b,1]]:; inv(A)
  Output:

  ⎡ ⎢ ⎣

  (b3+b2−b) (−b4−b3+b2) (−b4−b3+b2) (b3+b2−b)

  ⎤ ⎥ ⎦

• Factor a polynomial over a Galois field:
  Input:
  GF(5,3,c):; p:= x^2-c-1:; factor(p)
  Output:

  ⎛ ⎝

  ⎛ ⎝

  1%5

  ⎞ ⎠

  x+

  ⎛ ⎝

  (−2· c2+2· c)

  ⎞ ⎠

  ⎞ ⎠

  ⎛ ⎝

  ⎛ ⎝

  1%5

  ⎞ ⎠

  x+

  ⎛ ⎝

  (2· c2−2· c)

  ⎞ ⎠

  ⎞ ⎠

There are still some limitations due to an incomplete implementation of some algorithms, such as multivariate factorization when the polynomial is not unitary.

Example:
Input:

Output should be the unit, indeed:

As one can see in these examples, the output contains many times the same information that you would prefer not to see if you work many times with the same field. For this reason, the definition of a Galois field may have an optional argument, a variable name which will be used thereafter to represent elements of the field. Since you will also most likely want to modify the name of the indeterminate, the field name is grouped with the variable name in a list passed as third argument to GF. Note that these two variable names must be quoted.

Example.
Input:

Output:

Input:

Output:

Hence, the elements of GF(2,2) are G(0),G(1),G(w),G(w^2)=G(w+1).

We may also impose the irreducible primitive polynomial that we wish to use, by putting it as second argument (instead of n), for example:

If the polynomial is not primitive, Xcas will replace it automatically by a primitive polynomial, for example:
Input:

Output: