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.
Évariste Galois
Ask Jacobi or Gauss publicly to give their opinion, not as to the truth, but as to the importance of these theorems. Later there will be, I hope, some people who will find it to their advantage to decipher all this mess.
- May 29, 1832 (two days before his death)
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.
Prime field¶
In this tutorial, we will consider the prime field \(\mathrm{GF}(7)\). Using the galois library, the FieldArray
subclass GF7 is created using the class factory GF().
In [1]: GF7 = galois.GF(7)
In [2]: print(GF7.properties)
Galois Field:
name: GF(7)
characteristic: 7
degree: 1
order: 7
irreducible_poly: x + 4
is_primitive_poly: True
primitive_element: 3
In [3]: GF7 = galois.GF(7, repr="power")
In [4]: print(GF7.properties)
Galois Field:
name: GF(7)
characteristic: 7
degree: 1
order: 7
irreducible_poly: x + 4
is_primitive_poly: True
primitive_element: 3
Info
In this tutorial, we suggest using the integer representation to display the elements. However, sometimes it is useful to view elements in their power representation \(\{0, 1, \alpha, \alpha^2, \dots, \alpha^{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 \(\mathrm{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.
In [5]: GF7.elements
Out[5]: GF([0, 1, 2, 3, 4, 5, 6], order=7)
In [6]: GF7.elements
Out[6]: GF([ 0, 1, α^2, α, α^4, α^5, α^3], order=7)
Arithmetic¶
Addition, subtraction, and multiplication in \(\mathrm{GF}(p)\) is equivalent to integer addition, subtraction, and multiplication reduced modulo \(p\). Mathematically speaking, this is the integer ring \(\mathbb{Z} / p\mathbb{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 [7]: a_int = 3
In [8]: b_int = 5
In [9]: p = GF7.characteristic; p
Out[9]: 7
Here are \(a\) and \(b\) represented as prime field elements. See Array Creation for more details.
In [10]: a = GF7(3); a
Out[10]: GF(3, order=7)
In [11]: b = GF7(5); b
Out[11]: GF(5, order=7)
In [12]: a = GF7(3); a
Out[12]: GF(α, order=7)
In [13]: b = GF7(5); b
Out[13]: GF(α^5, order=7)
Addition¶
We can see that \(3 + 5 \equiv 1\ (\textrm{mod}\ 7)\). So accordingly, \(3 + 5 = 1\) in \(\mathrm{GF}(7)\).
In [14]: (a_int + b_int) % p
Out[14]: 1
In [15]: a + b
Out[15]: GF(1, order=7)
In [16]: (a_int + b_int) % p
Out[16]: 1
In [17]: a + b
Out[17]: 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.
In [18]: 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 [19]: 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\ (\textrm{mod}\ 7)\). So accordingly, \(3 - 5 = 5\) in \(\mathrm{GF}(7)\).
In [20]: (a_int - b_int) % p
Out[20]: 5
In [21]: a - b
Out[21]: GF(5, order=7)
In [22]: (a_int - b_int) % p
Out[22]: 5
In [23]: a - b
Out[23]: GF(α^5, order=7)
Here is the subtraction table for completeness.
In [24]: 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 [25]: 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\ (\textrm{mod}\ 7)\). So accordingly, \(3 \cdot 5 = 1\) in \(\mathrm{GF}(7)\).
In [26]: (a_int * b_int) % p
Out[26]: 1
In [27]: a * b
Out[27]: GF(1, order=7)
In [28]: (a_int * b_int) % p
Out[28]: 1
In [29]: a * b
Out[29]: GF(1, order=7)
Here is the multiplication table for completeness.
In [30]: 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
In [31]: 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 \(\mathrm{GF}(p)\) is a little more difficult. Division can’t be as simple as taking \(a / b\ (\textrm{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
\(xs + yt = \textrm{gcd}(x, y)\). This algorithm is implemented in egcd().
If \(x = 5\) is a field element of \(\mathrm{GF}(7)\) and \(y = 7\) is the prime characteristic, then \(s = x^{-1}\) in \(\mathrm{GF}(7)\). Note, the GCD will always be 1 because \(y\) is prime.
# Returns (gcd, s, t)
In [32]: galois.egcd(b_int, p)
Out[32]: (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 \(\mathrm{GF}(7)\) can be easily computed in the following way.
In [33]: b ** -1
Out[33]: GF(3, order=7)
In [34]: np.reciprocal(b)
Out[34]: GF(3, order=7)
In [35]: b ** -1
Out[35]: GF(α, order=7)
In [36]: np.reciprocal(b)
Out[36]: 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 \(\mathrm{GF}(7)\), we can equivalently compute \(3 \cdot 5^{-1}\) in \(\mathrm{GF}(7)\).
In [37]: _, b_inv_int, _ = galois.egcd(b_int, p)
In [38]: (a_int * b_inv_int) % p
Out[38]: 2
In [39]: a * b**-1
Out[39]: GF(2, order=7)
In [40]: a / b
Out[40]: GF(2, order=7)
In [41]: _, b_inv_int, _ = galois.egcd(b_int, p)
In [42]: (a_int * b_inv_int) % p
Out[42]: 2
In [43]: a * b**-1
Out[43]: GF(α^2, order=7)
In [44]: a / b
Out[44]: GF(α^2, order=7)
Here is the division table for completeness. Notice that division is not defined for \(y = 0\).
In [45]: 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
In [46]: 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 \(\mathrm{GF}(p)\) is an element such that \(\mathrm{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 \(\mathrm{GF}(p)^{\times}\). A primitive element has multiplicative order \(\textrm{ord}(g) = p - 1\).
In prime fields \(\mathrm{GF}(p)\), the generators or primitive elements of \(\mathrm{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\ (\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 primitive_root() and primitive_roots().
In [47]: galois.primitive_root(7)
Out[47]: 3
A primitive element¶
In galois, a primitive element of a finite field is provided by the primitive_element
class property.
In [48]: print(GF7.properties)
Galois Field:
name: GF(7)
characteristic: 7
degree: 1
order: 7
irreducible_poly: x + 4
is_primitive_poly: True
primitive_element: 3
In [49]: g = GF7.primitive_element; g
Out[49]: GF(3, order=7)
In [50]: print(GF7.properties)
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(α, 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 [52]: g.multiplicative_order()
Out[52]: 6
In [53]: 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.
In [54]: list(galois.primitive_roots(7))
Out[54]: [3, 5]
In [55]: GF7.primitive_elements
Out[55]: GF([3, 5], order=7)
In [56]: g = GF7(5); g
Out[56]: GF(5, order=7)
In [57]: list(galois.primitive_roots(7))
Out[57]: [3, 5]
In [58]: GF7.primitive_elements
Out[58]: GF([ α, α^5], order=7)
In [59]: g = GF7(5); g
Out[59]: GF(α^5, order=7)
This means that 3 and 5 generate the multiplicative group \(\mathrm{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 [60]: g.multiplicative_order()
Out[60]: 6
In [61]: 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.
In [62]: e = GF7(2); e
Out[62]: GF(2, order=7)
In [63]: e = GF7(2); e
Out[63]: GF(α^2, order=7)
It has \(\textrm{ord}(e) = 3\). Notice elements 3, 5, and 6 are not represented by the powers of \(e\).
In [64]: e.multiplicative_order()
Out[64]: 3
In [65]: 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