Intro to 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 another element from the set. A finite field is a field with a finite set of elements.

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 $GF (p)$ and extension fields $GF (p^{m})$ . This tutorial will focus on prime fields.

Prime field¶

In this tutorial, we will consider the prime field $GF (7)$ . Using the galois library, the FieldArray subclass GF7 is created using the class factory GF().

Integer

In [1]: GF7 = galois.GF(7)

In [2]: GF7
Out[2]: <class 'numpy.ndarray over GF(7)'>

In [3]: print(GF7)
Galois Field:
  name: GF(7)
  characteristic: 7
  degree: 1
  order: 7
  irreducible_poly: x + 4
  is_primitive_poly: True
  primitive_element: 3

Power

In [4]: GF7 = galois.GF(7, display="power")

In [5]: GF7
Out[5]: <class 'numpy.ndarray over GF(7)'>

In [6]: print(GF7)
Galois Field:
  name: GF(7)
  characteristic: 7
  degree: 1
  order: 7
  irreducible_poly: x + 4
  is_primitive_poly: True
  primitive_element: 3

Note

In this tutorial, we use the display="int" default to display the elements. However, sometimes it is useful to view elements in their power representation ${0, 1, α, α^{2}, \dots, α^{p^{m} - 2}}$ . Switch the display between these two representations using the tabbed sections. Note, the polynomial representation is not shown because it is identical to the integer representation for prime fields.

See Element Representation for more details.

Elements¶

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

The elements of the finite field are retrieved in a 1-D array using the Elements() classmethod.

Integer

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

Power

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

Arithmetic¶

Addition, subtraction, and multiplication in $GF (p)$ is equivalent to integer addition, subtraction, and multiplication reduced modulo $p$ . Mathematically speaking, this is the integer ring $Z / p Z$ .

In this tutorial, consider two field elements $a = 3$ and $b = 5$ . We will use galois to perform explicit modular integer arithmetic and then prime field arithmetic.

Here are $a$ and $b$ represented as Python integers.

In [9]: a_int = 3

In [10]: b_int = 5

In [11]: p = GF7.characteristic; p
Out[11]: 7

Here are $a$ and $b$ represented as prime field elements. See Array Creation for more details.

Integer

In [12]: a = GF7(3); a
Out[12]: GF(3, order=7)

In [13]: b = GF7(5); b
Out[13]: GF(5, order=7)

Power

In [14]: a = GF7(3); a
Out[14]: GF(α, order=7)

In [15]: b = GF7(5); b
Out[15]: GF(α^5, order=7)

Addition¶

We can see that $3 + 5 \equiv 1 (mod 7)$ . So accordingly, $3 + 5 = 1$ in $GF (7)$ .

Integer

In [16]: (a_int + b_int) % p
Out[16]: 1

In [17]: a + b
Out[17]: GF(1, order=7)

Power

In [18]: (a_int + b_int) % p
Out[18]: 1

In [19]: a + b
Out[19]: GF(1, order=7)

The galois library includes the ability to display the arithmetic tables for any 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.

Integer

In [20]: 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 |
+-------+---+---+---+---+---+---+---+

Power

In [21]: print(GF7.arithmetic_table("+"))
+-------+-----+-----+-----+-----+-----+-----+-----+
| x + y |   0 |   1 |   α | α^2 | α^3 | α^4 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     0 |   0 |   1 |   α | α^2 | α^3 | α^4 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     1 |   1 | α^2 | α^4 |   α |   0 | α^5 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     α |   α | α^4 | α^3 | α^5 | α^2 |   0 |   1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^2 | α^2 |   α | α^5 | α^4 |   1 | α^3 |   0 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^3 | α^3 |   0 | α^2 |   1 | α^5 |   α | α^4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^4 | α^4 | α^5 |   0 | α^3 |   α |   1 | α^2 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^5 | α^5 | α^3 |   1 |   0 | α^4 | α^2 |   α |
+-------+-----+-----+-----+-----+-----+-----+-----+

Subtraction¶

As with addition, we can see that $3 - 5 \equiv 5 (mod 7)$ . So accordingly, $3 - 5 = 5$ in $GF (7)$ .

Integer

In [22]: (a_int - b_int) % p
Out[22]: 5

In [23]: a - b
Out[23]: GF(5, order=7)

Power

In [24]: (a_int - b_int) % p
Out[24]: 5

In [25]: a - b
Out[25]: GF(α^5, order=7)

Here is the subtraction table for completeness.

Integer

In [26]: 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 |
+-------+---+---+---+---+---+---+---+

Power

In [27]: print(GF7.arithmetic_table("-"))
+-------+-----+-----+-----+-----+-----+-----+-----+
| x - y |   0 |   1 |   α | α^2 | α^3 | α^4 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     0 |   0 | α^3 | α^4 | α^5 |   1 |   α | α^2 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     1 |   1 |   0 | α^5 | α^3 | α^2 | α^4 |   α |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     α |   α | α^2 |   0 |   1 | α^4 | α^3 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^2 | α^2 |   1 | α^3 |   0 |   α | α^5 | α^4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^3 | α^3 | α^5 |   α | α^4 |   0 | α^2 |   1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^4 | α^4 |   α |   1 | α^2 | α^5 |   0 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^5 | α^5 | α^4 | α^2 |   α | α^3 |   1 |   0 |
+-------+-----+-----+-----+-----+-----+-----+-----+

Multiplication¶

Similarly, we can see that $3 \cdot 5 \equiv 1 (mod 7)$ . So accordingly, $3 \cdot 5 = 1$ in $GF (7)$ .

Integer

In [28]: (a_int * b_int) % p
Out[28]: 1

In [29]: a * b
Out[29]: GF(1, order=7)

Power

In [30]: (a_int * b_int) % p
Out[30]: 1

In [31]: a * b
Out[31]: GF(1, order=7)

Here is the multiplication table for completeness.

Integer

In [32]: 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 |
+-------+---+---+---+---+---+---+---+

Power

In [33]: print(GF7.arithmetic_table("*"))
+-------+-----+-----+-----+-----+-----+-----+-----+
| x * y |   0 |   1 |   α | α^2 | α^3 | α^4 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     0 |   0 |   0 |   0 |   0 |   0 |   0 |   0 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     1 |   0 |   1 |   α | α^2 | α^3 | α^4 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|     α |   0 |   α | α^2 | α^3 | α^4 | α^5 |   1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^2 |   0 | α^2 | α^3 | α^4 | α^5 |   1 |   α |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^3 |   0 | α^3 | α^4 | α^5 |   1 |   α | α^2 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^4 |   0 | α^4 | α^5 |   1 |   α | α^2 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+-----+
|   α^5 |   0 | α^5 |   1 |   α | α^2 | α^3 | α^4 |
+-------+-----+-----+-----+-----+-----+-----+-----+

Multiplicative inverse¶

Division in $GF (p)$ is a little more difficult. Division can’t be as simple as taking $a / b (mod p)$ because many integer divisions do not result in integers! The division $a / b$ can be reformulated into $a b^{- 1}$ , where $b^{- 1}$ is the multiplicative inverse of $b$ . Let’s first learn the multiplicative inverse before returning to division.

Euclid discovered an efficient algorithm to solve the Bézout Identity, which is used to find the multiplicative inverse. It is now called the Extended Euclidean Algorithm. Given two integers $x$ and $y$ , the Extended Euclidean Algorithm finds the integers $s$ and $t$ such that $x s + y t = gcd (x, y)$ . This algorithm is implemented in egcd().

If $x = 5$ is a field element of $GF (7)$ and $y = 7$ is the prime characteristic, then $s = x^{- 1}$ in $GF (7)$ . Note, the GCD will always be $1$ because $y$ is prime.

# Returns (gcd, s, t)
In [34]: galois.egcd(b_int, p)
Out[34]: (1, 3, -2)

The galois library uses the Extended Euclidean Algorithm to compute multiplicative inverses (and division) in prime fields. The inverse of $5$ in $GF (7)$ can be easily computed in the following way.

Integer

In [35]: b ** -1
Out[35]: GF(3, order=7)

In [36]: np.reciprocal(b)
Out[36]: GF(3, order=7)

Power

In [37]: b ** -1
Out[37]: GF(α, order=7)

In [38]: np.reciprocal(b)
Out[38]: GF(α, order=7)

Division¶

Now let’s return to division in finite fields. As mentioned earlier, $a / b$ is equivalent to $a b^{- 1}$ , and we have already learned multiplication and multiplicative inversion in finite fields.

To compute $3 / 5$ in $GF (7)$ , we can equivalently compute $3 \cdot 5^{- 1}$ in $GF (7)$ .

Integer

In [39]: _, b_inv_int, _ = galois.egcd(b_int, p)

In [40]: (a_int * b_inv_int) % p
Out[40]: 2

In [41]: a * b**-1
Out[41]: GF(2, order=7)

In [42]: a / b
Out[42]: GF(2, order=7)

Power

In [43]: _, b_inv_int, _ = galois.egcd(b_int, p)

In [44]: (a_int * b_inv_int) % p
Out[44]: 2

In [45]: a * b**-1
Out[45]: GF(α^2, order=7)

In [46]: a / b
Out[46]: GF(α^2, order=7)

Here is the division table for completeness. Notice that division is not defined for $y = 0$ .

Integer

In [47]: 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 |
+-------+---+---+---+---+---+---+

Power

In [48]: print(GF7.arithmetic_table("/"))
+-------+-----+-----+-----+-----+-----+-----+
| x / y |   1 |   α | α^2 | α^3 | α^4 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+
|     0 |   0 |   0 |   0 |   0 |   0 |   0 |
+-------+-----+-----+-----+-----+-----+-----+
|     1 |   1 | α^5 | α^4 | α^3 | α^2 |   α |
+-------+-----+-----+-----+-----+-----+-----+
|     α |   α |   1 | α^5 | α^4 | α^3 | α^2 |
+-------+-----+-----+-----+-----+-----+-----+
|   α^2 | α^2 |   α |   1 | α^5 | α^4 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+
|   α^3 | α^3 | α^2 |   α |   1 | α^5 | α^4 |
+-------+-----+-----+-----+-----+-----+-----+
|   α^4 | α^4 | α^3 | α^2 |   α |   1 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+
|   α^5 | α^5 | α^4 | α^3 | α^2 |   α |   1 |
+-------+-----+-----+-----+-----+-----+-----+

Primitive elements¶

A property of finite fields is that some elements produce the non-zero elements of the field by their powers.

A primitive element $g$ of $GF (p)$ is an element such that $GF (p) = {0, 1, g, g^{2}, \dots, g^{p - 2}}$ . The non-zero elements ${1, g, g^{2}, \dots, g^{p - 2}}$ form the cyclic multiplicative group $GF (p)^{\times}$ . A primitive element has multiplicative order $ord (g) = p - 1$ .

In prime fields $GF (p)$ , the generators or primitive elements of $GF (p)$ are primitive roots mod p.

Primitive roots mod $p$ ¶

An 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 (mod p)$ for some $k$ . In prime fields, since $p$ is prime, every integer $1 \leq a < p$ is coprime to $p$ .

Finding primitive roots mod $p$ is implemented in primitive_root() and primitive_roots().

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

A primitive element¶

In galois, a primitive element of a finite field is provided by the primitive_element class property.

Integer

In [50]: print(GF7)
Galois Field:
  name: GF(7)
  characteristic: 7
  degree: 1
  order: 7
  irreducible_poly: x + 4
  is_primitive_poly: True
  primitive_element: 3

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

Power

In [52]: print(GF7)
Galois Field:
  name: GF(7)
  characteristic: 7
  degree: 1
  order: 7
  irreducible_poly: x + 4
  is_primitive_poly: True
  primitive_element: 3

In [53]: g = GF7.primitive_element; g
Out[53]: GF(α, order=7)

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

Here is the representation table using the default generator $g = 3$ . Notice its multiplicative order is $p - 1$ .

In [54]: g.multiplicative_order()
Out[54]: 6

In [55]: 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    |
+-------+------------+--------+---------+

Other primitive elements¶

There are multiple primitive elements of any finite field. All primitive elements are provided in the primitive_elements class property.

Integer

In [56]: list(galois.primitive_roots(7))
Out[56]: [3, 5]

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

In [58]: g = GF7(5); g
Out[58]: GF(5, order=7)

Power

In [59]: list(galois.primitive_roots(7))
Out[59]: [3, 5]

In [60]: GF7.primitive_elements
Out[60]: GF([  α, α^5], order=7)

In [61]: g = GF7(5); g
Out[61]: GF(α^5, order=7)

This means that $3$ and $5$ generate the multiplicative group $GF (7)^{\times}$ . We can examine this by viewing the representation table using different generators.

Here is the representation table using a different generator $g = 5$ . Notice it also has multiplicative order $p - 1$ .

In [62]: g.multiplicative_order()
Out[62]: 6

In [63]: print(GF7.repr_table(g))
+-------+------------+--------+---------+
| 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    |
+-------+------------+--------+---------+

Non-primitive elements¶

All other elements of the field cannot generate the multiplicative group. They have multiplicative orders less than $p - 1$ .

For example, the element $e = 2$ is not a primitive element.

Integer

In [64]: e = GF7(2); e
Out[64]: GF(2, order=7)

Power

In [65]: e = GF7(2); e
Out[65]: GF(α^2, order=7)

It has $ord (e) = 3$ . Notice elements $3$ , $5$ , and $6$ are not represented by the powers of $e$ .

In [66]: e.multiplicative_order()
Out[66]: 3

In [67]: print(GF7.repr_table(e))
+-------+------------+--------+---------+
| 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    |
+-------+------------+--------+---------+

Last update: Apr 18, 2022

Intro to Prime Fields¶

Prime field¶

Elements¶

Arithmetic¶

Addition¶

Subtraction¶

Multiplication¶

Multiplicative inverse¶

Division¶

Primitive elements¶

Primitive roots mod p¶

A primitive element¶

Other primitive elements¶

Non-primitive elements¶

Primitive roots mod $p$ ¶