Intro to Galois Fields: Prime Fields

A Galois field is a finite field named in honor of Évariste Galois, one of the fathers of group theory. A field is a set that is closed under addition, subtraction, multiplication, and division. To be closed under an operation means that performing the operation on any two elements of the set will result in a third element from the set. A finite field is a field with a finite set.

Galois proved that finite fields exist only when their order (or size of the set) is a prime power \(p^m\). Accordingly, finite fields can be broken into two categories: prime fields \(\mathrm{GF}(p)\) and extension fields \(\mathrm{GF}(p^m)\). This tutorial will focus on prime fields.

Elements

The elements of the Galois field \(\mathrm{GF}(p)\) are naturally represented as the integers \(\{0, 1, \dots, p - 1\}\).

Using the galois package, a Galois field array class is created using the class factory galois.GF().

In [1]: GF7 = galois.GF(7); GF7
Out[1]: <class 'numpy.ndarray over GF(7)'>

In [2]: print(GF7.properties)
GF(7):
  characteristic: 7
  degree: 1
  order: 7
  irreducible_poly: x + 4
  is_primitive_poly: True
  primitive_element: 3

The elements of the Galois field can be represented as a 1-dimensional array using the galois.FieldArray.Elements() method.

In [3]: GF7.Elements()
Out[3]: GF([0, 1, 2, 3, 4, 5, 6], order=7)

This array should be read as “a Galois field array [0, 1, 2, 3, 4, 5, 6] over the finite field with order 7”.

Arithmetic mod p

Addition, subtraction, and multiplication in \(\mathrm{GF}(p)\) is equivalent to integer addition, subtraction, and multiplication reduced modulo \(p\). Mathematically speaking, this is the ring of integers mod \(p\), \(\mathbb{Z}/p\mathbb{Z}\).

With galois, we can represent a single Galois field element using GF7(int). For example, GF7(3) to represent the field element \(3\). We can see that \(3 + 5 \equiv 1\ (\textrm{mod}\ 7)\), so accordingly \(3 + 5 = 1\) in \(\mathrm{GF}(7)\). The same can be shown for subtraction and multiplication.

In [4]: GF7(3) + GF7(5)
Out[4]: GF(1, order=7)

In [5]: GF7(3) - GF7(5)
Out[5]: GF(5, order=7)

In [6]: GF7(3) * GF7(5)
Out[6]: GF(1, order=7)

The power of galois, however, is array arithmetic not scalar arithmetic. Random arrays over \(\mathrm{GF}(7)\) can be created using galois.FieldArray.Random(). Normal binary operators work on Galois field arrays just like numpy arrays.

In [7]: x = GF7.Random(10); x
Out[7]: GF([2, 0, 0, 4, 5, 4, 2, 5, 6, 5], order=7)

In [8]: y = GF7.Random(10); y
Out[8]: GF([5, 3, 3, 5, 1, 1, 6, 4, 0, 6], order=7)

In [9]: x + y
Out[9]: GF([0, 3, 3, 2, 6, 5, 1, 2, 6, 4], order=7)

In [10]: x - y
Out[10]: GF([4, 4, 4, 6, 4, 3, 3, 1, 6, 6], order=7)

In [11]: x * y
Out[11]: GF([3, 0, 0, 6, 5, 4, 5, 6, 0, 2], order=7)

The galois package includes the ability to display the arithmetic tables for a given finite field. The table is only readable for small fields, but nonetheless the capability is provided. Select a few computations at random and convince yourself the answers are correct.

In [12]: print(GF7.arithmetic_table("+"))
╔═══════╦═══╤═══╤═══╤═══╤═══╤═══╤═══╗
║ x + y ║ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 ║
╠═══════╬═══╪═══╪═══╪═══╪═══╪═══╪═══╣
║     0 ║ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     1 ║ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 0 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     2 ║ 2 │ 3 │ 4 │ 5 │ 6 │ 0 │ 1 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     3 ║ 3 │ 4 │ 5 │ 6 │ 0 │ 1 │ 2 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     4 ║ 4 │ 5 │ 6 │ 0 │ 1 │ 2 │ 3 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     5 ║ 5 │ 6 │ 0 │ 1 │ 2 │ 3 │ 4 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     6 ║ 6 │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 ║
╚═══════╩═══╧═══╧═══╧═══╧═══╧═══╧═══╝

In [13]: print(GF7.arithmetic_table("-"))
╔═══════╦═══╤═══╤═══╤═══╤═══╤═══╤═══╗
║ x - y ║ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 ║
╠═══════╬═══╪═══╪═══╪═══╪═══╪═══╪═══╣
║     0 ║ 0 │ 6 │ 5 │ 4 │ 3 │ 2 │ 1 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     1 ║ 1 │ 0 │ 6 │ 5 │ 4 │ 3 │ 2 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     2 ║ 2 │ 1 │ 0 │ 6 │ 5 │ 4 │ 3 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     3 ║ 3 │ 2 │ 1 │ 0 │ 6 │ 5 │ 4 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     4 ║ 4 │ 3 │ 2 │ 1 │ 0 │ 6 │ 5 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     5 ║ 5 │ 4 │ 3 │ 2 │ 1 │ 0 │ 6 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     6 ║ 6 │ 5 │ 4 │ 3 │ 2 │ 1 │ 0 ║
╚═══════╩═══╧═══╧═══╧═══╧═══╧═══╧═══╝

In [14]: print(GF7.arithmetic_table("*"))
╔═══════╦═══╤═══╤═══╤═══╤═══╤═══╤═══╗
║ x * y ║ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 ║
╠═══════╬═══╪═══╪═══╪═══╪═══╪═══╪═══╣
║     0 ║ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     1 ║ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     2 ║ 0 │ 2 │ 4 │ 6 │ 1 │ 3 │ 5 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     3 ║ 0 │ 3 │ 6 │ 2 │ 5 │ 1 │ 4 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     4 ║ 0 │ 4 │ 1 │ 5 │ 2 │ 6 │ 3 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     5 ║ 0 │ 5 │ 3 │ 1 │ 6 │ 4 │ 2 ║
╟───────╫───┼───┼───┼───┼───┼───┼───╢
║     6 ║ 0 │ 6 │ 5 │ 4 │ 3 │ 2 │ 1 ║
╚═══════╩═══╧═══╧═══╧═══╧═══╧═══╧═══╝

Division in \(\mathrm{GF}(p)\) is a little more difficult. Division can’t be as simple as taking \(x / y\ (\textrm{mod}\ p)\) because many integer divisions do not result in integers. The division of \(x / y = z\) can be reformulated as the question “what \(z\) multiplied by \(y\) results in \(x\)?”. This is an equivalent problem to “what \(z\) multiplied by \(y\) results in \(1\)?”, where \(z\) is the multiplicative inverse of \(y\).

To find the multiplicative inverse of \(y\), one can simply perform trial multiplication until the result of \(1\) is found. For instance, suppose \(y = 4\) in \(\mathrm{GF}(7)\). We can multiply \(4\) by every element in the field until the product is \(1\) and we’ll find that \(4^{-1} = 2\) in \(\mathrm{GF}(7)\), namely \(2 * 4 = 1\) in \(\mathrm{GF}(7)\).

In [15]: y = GF7(4); y
Out[15]: GF(4, order=7)

# Hypothesize each element from GF(7)
In [16]: guesses = GF7.Elements(); guesses
Out[16]: GF([0, 1, 2, 3, 4, 5, 6], order=7)

In [17]: results = y * guesses; results
Out[17]: GF([0, 4, 1, 5, 2, 6, 3], order=7)

In [18]: y_inv = guesses[np.where(results == 1)[0][0]]; y_inv
Out[18]: GF(2, order=7)

This algorithm is terribly inefficient for large fields, however. Fortunately, Euclid came up with an efficient algorithm, now called the Extended Eulcidean Algorithm. Given two integers \(a\) and \(b\), the Extended Euclidean Algorithm finds the integers \(x\) and \(y\) such that \(xa + yb = \textrm{gcd}(a, b)\). This algorithm is implemented in galois.egcd().

If \(a = 4\) is a field element of \(\mathrm{GF}(7)\) and \(b = 7\), the prime characteristic, then \(x = a^{-1}\) in \(\mathrm{GF}(7)\). Note, the GCD will always be \(1\) because \(b\) is prime.

In [19]: galois.egcd(4, 7)
Out[19]: (1, 2, -1)

The galois package uses the Extended Euclidean Algorithm to compute multiplicative inverses (and division) in prime fields. The inverse of \(4\) in \(\mathrm{GF}(7)\) can be easily computed in the following way.

In [20]: y = GF7(4); y
Out[20]: GF(4, order=7)

In [21]: np.reciprocal(y)
Out[21]: GF(2, order=7)

In [22]: y ** -1
Out[22]: GF(2, order=7)

With this in mind, the division table for \(\mathrm{GF}(7)\) can be calculated. Note that division is not defined for \(y = 0\).

In [23]: print(GF7.arithmetic_table("/"))
╔═══════╦═══╤═══╤═══╤═══╤═══╤═══╗
║ x / y ║ 1 │ 2 │ 3 │ 4 │ 5 │ 6 ║
╠═══════╬═══╪═══╪═══╪═══╪═══╪═══╣
║     0 ║ 0 │ 0 │ 0 │ 0 │ 0 │ 0 ║
╟───────╫───┼───┼───┼───┼───┼───╢
║     1 ║ 1 │ 4 │ 5 │ 2 │ 3 │ 6 ║
╟───────╫───┼───┼───┼───┼───┼───╢
║     2 ║ 2 │ 1 │ 3 │ 4 │ 6 │ 5 ║
╟───────╫───┼───┼───┼───┼───┼───╢
║     3 ║ 3 │ 5 │ 1 │ 6 │ 2 │ 4 ║
╟───────╫───┼───┼───┼───┼───┼───╢
║     4 ║ 4 │ 2 │ 6 │ 1 │ 5 │ 3 ║
╟───────╫───┼───┼───┼───┼───┼───╢
║     5 ║ 5 │ 6 │ 4 │ 3 │ 1 │ 2 ║
╟───────╫───┼───┼───┼───┼───┼───╢
║     6 ║ 6 │ 3 │ 2 │ 5 │ 4 │ 1 ║
╚═══════╩═══╧═══╧═══╧═══╧═══╧═══╝

Primitive elements

A property of finite fields is that some elements can produce the entire field by their powers. Namely, a primitive element \(g\) of \(\mathrm{GF}(p)\) is an element such that \(\mathrm{GF}(p) = \{0, g^0, g^1, \dots, g^{p - 1}\}\). In prime fields \(\mathrm{GF}(p)\), the generators or primitive elements of \(\mathrm{GF}(p)\) are primitive roots mod p.

The integer \(g\) is a primitive root mod p if every number coprime to \(p\) can be represented as a power of \(g\) mod \(p\). Namely, every \(a\) coprime to \(p\) can be represented as \(g^k \equiv a\ (\textrm{mod}\ p)\) for some \(k\). In prime fields, since \(p\) is prime, every integer \(1 \le a < p\) is coprime to \(p\). Finding primitive roots mod \(p\) is implemented in galois.primitive_root() and galois.primitive_roots().

In [24]: galois.primitive_root(7)
Out[24]: 3

Since \(3\) is a primitive root mod \(7\), the claim is that the elements of \(\mathrm{GF}(7)\) can be written as \(\mathrm{GF}(7) = \{0, 3^0, 3^1, \dots, 3^6\}\). \(0\) is a special element. It can technically be represented as \(g^{-\infty}\), however that can’t be computed on a computer. For the non-zero elements, they can easily be calculated as powers of \(g\). The set \(\{3^0, 3^1, \dots, 3^6\}\) forms a cyclic multiplicative group, namely \(\mathrm{GF}(7)^{\times}\).

In [25]: g = GF7(3); g
Out[25]: GF(3, order=7)

In [26]: g ** np.arange(0, GF7.order - 1)
Out[26]: GF([1, 3, 2, 6, 4, 5], order=7)

A primitive element of \(\mathrm{GF}(p)\) can be accessed through galois.FieldClass.primitive_element.

In [27]: GF7.primitive_element
Out[27]: GF(3, order=7)

The galois package allows you to easily display all powers of an element and their equivalent polynomial, vector, and integer representations. Let’s ignore the polynomial and vector representations for now; they will become useful for extension fields.

In [28]: print(GF7.repr_table())
╔═══════╤════════════╤════════╤═════════╗
║ Power │ Polynomial │ Vector │ Integer ║
║═══════╪════════════╪════════╪═════════║
║   0   │     0      │  [0]   │    0    ║
╟───────┼────────────┼────────┼─────────╢
║  3^0  │     1      │  [1]   │    1    ║
╟───────┼────────────┼────────┼─────────╢
║  3^1  │     3      │  [3]   │    3    ║
╟───────┼────────────┼────────┼─────────╢
║  3^2  │     2      │  [2]   │    2    ║
╟───────┼────────────┼────────┼─────────╢
║  3^3  │     6      │  [6]   │    6    ║
╟───────┼────────────┼────────┼─────────╢
║  3^4  │     4      │  [4]   │    4    ║
╟───────┼────────────┼────────┼─────────╢
║  3^5  │     5      │  [5]   │    5    ║
╚═══════╧════════════╧════════╧═════════╝

There are multiple primitive elements of a given field. In the case of \(\mathrm{GF}(7)\), \(3\) and \(5\) are primitive elements.

In [29]: GF7.primitive_elements
Out[29]: GF([3, 5], order=7)

In [30]: print(GF7.repr_table(GF7(5)))
╔═══════╤════════════╤════════╤═════════╗
║ Power │ Polynomial │ Vector │ Integer ║
║═══════╪════════════╪════════╪═════════║
║   0   │     0      │  [0]   │    0    ║
╟───────┼────────────┼────────┼─────────╢
║  5^0  │     1      │  [1]   │    1    ║
╟───────┼────────────┼────────┼─────────╢
║  5^1  │     5      │  [5]   │    5    ║
╟───────┼────────────┼────────┼─────────╢
║  5^2  │     4      │  [4]   │    4    ║
╟───────┼────────────┼────────┼─────────╢
║  5^3  │     6      │  [6]   │    6    ║
╟───────┼────────────┼────────┼─────────╢
║  5^4  │     2      │  [2]   │    2    ║
╟───────┼────────────┼────────┼─────────╢
║  5^5  │     3      │  [3]   │    3    ║
╚═══════╧════════════╧════════╧═════════╝

And it can be seen that every other element of \(\mathrm{GF}(7)\) is not a generator of the multiplicative group. For instance, \(2\) does not generate the multiplicative group \(\mathrm{GF}(7)^\times\).

In [31]: print(GF7.repr_table(GF7(2)))
╔═══════╤════════════╤════════╤═════════╗
║ Power │ Polynomial │ Vector │ Integer ║
║═══════╪════════════╪════════╪═════════║
║   0   │     0      │  [0]   │    0    ║
╟───────┼────────────┼────────┼─────────╢
║  2^0  │     1      │  [1]   │    1    ║
╟───────┼────────────┼────────┼─────────╢
║  2^1  │     2      │  [2]   │    2    ║
╟───────┼────────────┼────────┼─────────╢
║  2^2  │     4      │  [4]   │    4    ║
╟───────┼────────────┼────────┼─────────╢
║  2^3  │     1      │  [1]   │    1    ║
╟───────┼────────────┼────────┼─────────╢
║  2^4  │     2      │  [2]   │    2    ║
╟───────┼────────────┼────────┼─────────╢
║  2^5  │     4      │  [4]   │    4    ║
╚═══════╧════════════╧════════╧═════════╝