Intro to Extension Fields¶
As discussed in the Intro to Prime Fields tutorial, a finite field is a finite set that is closed under addition, subtraction, multiplication, and division. Galois proved that finite fields exist only when their order (or size of the set) is a prime power \(p^m\).
When the order is prime, the arithmetic is mostly computed using integer arithmetic modulo \(p\). When the order is a prime power, namely extension fields \(\mathrm{GF}(p^m)\), the arithmetic is mostly computed using polynomial arithmetic modulo the irreducible polynomial \(f(x)\).
Extension field¶
In this tutorial, we will consider the extension field \(\mathrm{GF}(3^2)\). Using the galois library, the FieldArray subclass
GF9 is created using the class factory GF().
In [1]: GF9 = galois.GF(3**2)
In [2]: print(GF9.properties)
Galois Field:
name: GF(3^2)
characteristic: 3
degree: 2
order: 9
irreducible_poly: x^2 + 2x + 2
is_primitive_poly: True
primitive_element: x
In [3]: GF9 = galois.GF(3**2, display="poly")
In [4]: print(GF9.properties)
Galois Field:
name: GF(3^2)
characteristic: 3
degree: 2
order: 9
irreducible_poly: x^2 + 2x + 2
is_primitive_poly: True
primitive_element: x
In [5]: GF9 = galois.GF(3**2, display="power")
In [6]: print(GF9.properties)
Galois Field:
name: GF(3^2)
characteristic: 3
degree: 2
order: 9
irreducible_poly: x^2 + 2x + 2
is_primitive_poly: True
primitive_element: x
Note
In this tutorial, we use display="poly" to display the elements in their polynomial form. Although, it is common to use the default
integer representation \(\{0, 1, \dots, p^m - 1\}\) to display the arrays more compactly. Switch the display between the three
representations using the tabbed sections.
See Element Representation for more details.
Elements¶
The elements of \(\mathrm{GF}(p^m)\) are polynomials over \(\mathrm{GF}(p)\) with degree less than \(m\). Formally, they are all polynomials \(a_{m-1}x^{m-1} + \dots + a_1x^1 + a_0 \in \mathrm{GF}(p)[x]\). There are exactly \(p^m\) elements.
The elements of the finite field are retrieved in a 1-D array using the Elements() classmethod.
In [7]: GF9.Elements()
Out[7]: GF([0, 1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
In [8]: GF9.Elements()
Out[8]:
GF([ 0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1,
2α + 2], order=3^2)
In [9]: GF9.Elements()
Out[9]: GF([ 0, 1, α^4, α, α^2, α^7, α^5, α^3, α^6], order=3^2)
Irreducible polynomial¶
Every extension field must be defined with respect to an irreducible polynomial \(f(x)\). This polynomial defines the arithmetic of the field.
When creating a FieldArray subclass in galois, if an irreducible polynomial is not explicitly specified, a default
is chosen. The default is the Conway polynomial \(C_{p,m}(x)\), which is irreducible and primitive. See conway_poly()
for more information.
Notice \(f(x)\) is over \(\mathrm{GF}(3)\) with degree \(2\).
In [10]: f = GF9.irreducible_poly; f
Out[10]: Poly(x^2 + 2x + 2, GF(3))
Also note, when factored, \(f(x)\) has no irreducible factors other than itself – an analogue of a prime number.
In [11]: f.is_irreducible()
Out[11]: True
In [12]: f.factors()
Out[12]: ([Poly(x^2 + 2x + 2, GF(3))], [1])
Arithmetic¶
Addition, subtraction, and multiplication in \(\mathrm{GF}(p^m)\) with irreducible polynomial \(f(x)\) is equivalent to polynomial addition, subtraction, and multiplication over \(\mathrm{GF}(p)\) reduced modulo \(f(x)\). Mathematically speaking, this is the polynomial ring \(\mathrm{GF}(p)[x] / f(x)\).
In this tutorial, consider two field elements \(a = x + 2\) and \(b = x + 1\). We will use galois to perform explicit polynomial
calculations and then extension field arithmetic.
Here are \(a\) and \(b\) represented using Poly objects.
In [13]: GF3 = galois.GF(3)
In [14]: a_poly = galois.Poly([1, 2], field=GF3); a_poly
Out[14]: Poly(x + 2, GF(3))
In [15]: b_poly = galois.Poly([1, 1], field=GF3); b_poly
Out[15]: Poly(x + 1, GF(3))
Here are \(a\) and \(b\) represented as extension field elements. Extension field elements can be specified as integers or polynomial strings. See Array Creation for more details.
In [16]: a = GF9("x + 2"); a
Out[16]: GF(5, order=3^2)
In [17]: b = GF9("x + 1"); b
Out[17]: GF(4, order=3^2)
In [18]: a = GF9("x + 2"); a
Out[18]: GF(α + 2, order=3^2)
In [19]: b = GF9("x + 1"); b
Out[19]: GF(α + 1, order=3^2)
In [20]: a = GF9("x + 2"); a
Out[20]: GF(α^7, order=3^2)
In [21]: b = GF9("x + 1"); b
Out[21]: GF(α^2, order=3^2)
Addition¶
In polynomial addition, the polynomial coefficients add degree-wise in \(\mathrm{GF}(p)\). Addition of polynomials with degree less than \(m\) will never result in a polynomial of degree \(m\) or greater. Therefore, it is unnecessary to reduce modulo the degree-\(m\) polynomial \(f(x)\), since the quotient will always be zero.
We can see that \(a + b = (1 + 1)x + (2 + 1) = 2x\).
In [22]: a_poly + b_poly
Out[22]: Poly(2x, GF(3))
In [23]: a + b
Out[23]: GF(6, order=3^2)
In [24]: a_poly + b_poly
Out[24]: Poly(2x, GF(3))
In [25]: a + b
Out[25]: GF(2α, order=3^2)
In [26]: a_poly + b_poly
Out[26]: Poly(2x, GF(3))
In [27]: a + b
Out[27]: GF(α^5, order=3^2)
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 [28]: print(GF9.arithmetic_table("+"))
+-------+---+---+---+---+---+---+---+---+---+
| x + y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+-------+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+-------+---+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 0 | 4 | 5 | 3 | 7 | 8 | 6 |
+-------+---+---+---+---+---+---+---+---+---+
| 2 | 2 | 0 | 1 | 5 | 3 | 4 | 8 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+---+
| 3 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 |
+-------+---+---+---+---+---+---+---+---+---+
| 4 | 4 | 5 | 3 | 7 | 8 | 6 | 1 | 2 | 0 |
+-------+---+---+---+---+---+---+---+---+---+
| 5 | 5 | 3 | 4 | 8 | 6 | 7 | 2 | 0 | 1 |
+-------+---+---+---+---+---+---+---+---+---+
| 6 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 |
+-------+---+---+---+---+---+---+---+---+---+
| 7 | 7 | 8 | 6 | 1 | 2 | 0 | 4 | 5 | 3 |
+-------+---+---+---+---+---+---+---+---+---+
| 8 | 8 | 6 | 7 | 2 | 0 | 1 | 5 | 3 | 4 |
+-------+---+---+---+---+---+---+---+---+---+
In [29]: print(GF9.arithmetic_table("+"))
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| x + y | 0 | 1 | 2 | α | α + 1 | α + 2 | 2α | 2α + 1 | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 0 | 0 | 1 | 2 | α | α + 1 | α + 2 | 2α | 2α + 1 | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 1 | 1 | 2 | 0 | α + 1 | α + 2 | α | 2α + 1 | 2α + 2 | 2α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2 | 2 | 0 | 1 | α + 2 | α | α + 1 | 2α + 2 | 2α | 2α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α | α | α + 1 | α + 2 | 2α | 2α + 1 | 2α + 2 | 0 | 1 | 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 1 | α + 1 | α + 2 | α | 2α + 1 | 2α + 2 | 2α | 1 | 2 | 0 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 2 | α + 2 | α | α + 1 | 2α + 2 | 2α | 2α + 1 | 2 | 0 | 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α | 2α | 2α + 1 | 2α + 2 | 0 | 1 | 2 | α | α + 1 | α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 1 | 2α + 1 | 2α + 2 | 2α | 1 | 2 | 0 | α + 1 | α + 2 | α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 2 | 2α + 2 | 2α | 2α + 1 | 2 | 0 | 1 | α + 2 | α | α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
In [30]: print(GF9.arithmetic_table("+"))
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| x + y | 0 | 1 | α | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 0 | 0 | 1 | α | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 1 | α^4 | α^2 | α^7 | α^6 | 0 | α^3 | α^5 | α |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α | α | α^2 | α^5 | α^3 | 1 | α^7 | 0 | α^4 | α^6 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^2 | α^2 | α^7 | α^3 | α^6 | α^4 | α | 1 | 0 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^3 | α^3 | α^6 | 1 | α^4 | α^7 | α^5 | α^2 | α | 0 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^4 | α^4 | 0 | α^7 | α | α^5 | 1 | α^6 | α^3 | α^2 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^5 | α^5 | α^3 | 0 | 1 | α^2 | α^6 | α | α^7 | α^4 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^6 | α^6 | α^5 | α^4 | 0 | α | α^3 | α^7 | α^2 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^7 | α^7 | α | α^6 | α^5 | 0 | α^2 | α^4 | 1 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Subtraction¶
Subtraction, like addition, is performed on coefficients degree-wise and will never result in a polynomial with greater degree.
We can see that \(a - b = (1 - 1)x + (2 - 1) = 1\).
In [31]: a_poly - b_poly
Out[31]: Poly(1, GF(3))
In [32]: a - b
Out[32]: GF(1, order=3^2)
In [33]: a_poly - b_poly
Out[33]: Poly(1, GF(3))
In [34]: a - b
Out[34]: GF(1, order=3^2)
In [35]: a_poly - b_poly
Out[35]: Poly(1, GF(3))
In [36]: a - b
Out[36]: GF(1, order=3^2)
Here is the entire subtraction table for completeness.
In [37]: print(GF9.arithmetic_table("-"))
+-------+---+---+---+---+---+---+---+---+---+
| x - y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+-------+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 6 | 8 | 7 | 3 | 5 | 4 |
+-------+---+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 2 | 7 | 6 | 8 | 4 | 3 | 5 |
+-------+---+---+---+---+---+---+---+---+---+
| 2 | 2 | 1 | 0 | 8 | 7 | 6 | 5 | 4 | 3 |
+-------+---+---+---+---+---+---+---+---+---+
| 3 | 3 | 5 | 4 | 0 | 2 | 1 | 6 | 8 | 7 |
+-------+---+---+---+---+---+---+---+---+---+
| 4 | 4 | 3 | 5 | 1 | 0 | 2 | 7 | 6 | 8 |
+-------+---+---+---+---+---+---+---+---+---+
| 5 | 5 | 4 | 3 | 2 | 1 | 0 | 8 | 7 | 6 |
+-------+---+---+---+---+---+---+---+---+---+
| 6 | 6 | 8 | 7 | 3 | 5 | 4 | 0 | 2 | 1 |
+-------+---+---+---+---+---+---+---+---+---+
| 7 | 7 | 6 | 8 | 4 | 3 | 5 | 1 | 0 | 2 |
+-------+---+---+---+---+---+---+---+---+---+
| 8 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+-------+---+---+---+---+---+---+---+---+---+
In [38]: print(GF9.arithmetic_table("-"))
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| x - y | 0 | 1 | 2 | α | α + 1 | α + 2 | 2α | 2α + 1 | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 0 | 0 | 2 | 1 | 2α | 2α + 2 | 2α + 1 | α | α + 2 | α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 1 | 1 | 0 | 2 | 2α + 1 | 2α | 2α + 2 | α + 1 | α | α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2 | 2 | 1 | 0 | 2α + 2 | 2α + 1 | 2α | α + 2 | α + 1 | α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α | α | α + 2 | α + 1 | 0 | 2 | 1 | 2α | 2α + 2 | 2α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 1 | α + 1 | α | α + 2 | 1 | 0 | 2 | 2α + 1 | 2α | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 2 | α + 2 | α + 1 | α | 2 | 1 | 0 | 2α + 2 | 2α + 1 | 2α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α | 2α | 2α + 2 | 2α + 1 | α | α + 2 | α + 1 | 0 | 2 | 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 1 | 2α + 1 | 2α | 2α + 2 | α + 1 | α | α + 2 | 1 | 0 | 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 2 | 2α + 2 | 2α + 1 | 2α | α + 2 | α + 1 | α | 2 | 1 | 0 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
In [39]: print(GF9.arithmetic_table("-"))
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| x - y | 0 | 1 | α | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 0 | 0 | α^4 | α^5 | α^6 | α^7 | 1 | α | α^2 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 1 | 0 | α^3 | α^5 | α | α^4 | α^2 | α^7 | α^6 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α | α | α^7 | 0 | α^4 | α^6 | α^2 | α^5 | α^3 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^2 | α^2 | α | 1 | 0 | α^5 | α^7 | α^3 | α^6 | α^4 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^3 | α^3 | α^5 | α^2 | α | 0 | α^6 | 1 | α^4 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^4 | α^4 | 1 | α^6 | α^3 | α^2 | 0 | α^7 | α | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^5 | α^5 | α^6 | α | α^7 | α^4 | α^3 | 0 | 1 | α^2 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^6 | α^6 | α^3 | α^7 | α^2 | 1 | α^5 | α^4 | 0 | α |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^7 | α^7 | α^2 | α^4 | 1 | α^3 | α | α^6 | α^5 | 0 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Multiplication¶
Multiplication of polynomials with degree less than \(m\), however, will often result in a polynomial of degree \(m\) or greater. Therefore, it is necessary to reduce the result modulo \(f(x)\).
First compute \(ab = (x + 2)(x + 1) = x^2 + 2\). Notice that \(x^2 + 2\) has degree \(2\), but the elements of \(\mathrm{GF}(3^2)\) can have degree at most \(1\). Therefore, reduction modulo \(f(x)\) is required. After remainder division, we see that \(ab\ \equiv x\ \textrm{mod}\ f(x)\).
# Note the degree is greater than 1
In [40]: a_poly * b_poly
Out[40]: Poly(x^2 + 2, GF(3))
In [41]: (a_poly * b_poly) % f
Out[41]: Poly(x, GF(3))
In [42]: a * b
Out[42]: GF(3, order=3^2)
# Note the degree is greater than 1
In [43]: a_poly * b_poly
Out[43]: Poly(x^2 + 2, GF(3))
In [44]: (a_poly * b_poly) % f
Out[44]: Poly(x, GF(3))
In [45]: a * b
Out[45]: GF(α, order=3^2)
# Note the degree is greater than 1
In [46]: a_poly * b_poly
Out[46]: Poly(x^2 + 2, GF(3))
In [47]: (a_poly * b_poly) % f
Out[47]: Poly(x, GF(3))
In [48]: a * b
Out[48]: GF(α, order=3^2)
Here is the entire multiplication table for completeness.
In [49]: print(GF9.arithmetic_table("*"))
+-------+---+---+---+---+---+---+---+---+---+
| x * y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+-------+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-------+---+---+---+---+---+---+---+---+---+
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+-------+---+---+---+---+---+---+---+---+---+
| 2 | 0 | 2 | 1 | 6 | 8 | 7 | 3 | 5 | 4 |
+-------+---+---+---+---+---+---+---+---+---+
| 3 | 0 | 3 | 6 | 4 | 7 | 1 | 8 | 2 | 5 |
+-------+---+---+---+---+---+---+---+---+---+
| 4 | 0 | 4 | 8 | 7 | 2 | 3 | 5 | 6 | 1 |
+-------+---+---+---+---+---+---+---+---+---+
| 5 | 0 | 5 | 7 | 1 | 3 | 8 | 2 | 4 | 6 |
+-------+---+---+---+---+---+---+---+---+---+
| 6 | 0 | 6 | 3 | 8 | 5 | 2 | 4 | 1 | 7 |
+-------+---+---+---+---+---+---+---+---+---+
| 7 | 0 | 7 | 5 | 2 | 6 | 4 | 1 | 8 | 3 |
+-------+---+---+---+---+---+---+---+---+---+
| 8 | 0 | 8 | 4 | 5 | 1 | 6 | 7 | 3 | 2 |
+-------+---+---+---+---+---+---+---+---+---+
In [50]: print(GF9.arithmetic_table("*"))
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| x * y | 0 | 1 | 2 | α | α + 1 | α + 2 | 2α | 2α + 1 | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 1 | 0 | 1 | 2 | α | α + 1 | α + 2 | 2α | 2α + 1 | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2 | 0 | 2 | 1 | 2α | 2α + 2 | 2α + 1 | α | α + 2 | α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α | 0 | α | 2α | α + 1 | 2α + 1 | 1 | 2α + 2 | 2 | α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 1 | 0 | α + 1 | 2α + 2 | 2α + 1 | 2 | α | α + 2 | 2α | 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 2 | 0 | α + 2 | 2α + 1 | 1 | α | 2α + 2 | 2 | α + 1 | 2α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α | 0 | 2α | α | 2α + 2 | α + 2 | 2 | α + 1 | 1 | 2α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 1 | 0 | 2α + 1 | α + 2 | 2 | 2α | α + 1 | 1 | 2α + 2 | α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 2 | 0 | 2α + 2 | α + 1 | α + 2 | 1 | 2α | 2α + 1 | α | 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
In [51]: print(GF9.arithmetic_table("*"))
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| x * y | 0 | 1 | α | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 0 | 1 | α | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α | 0 | α | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^2 | 0 | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 | 1 | α |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^3 | 0 | α^3 | α^4 | α^5 | α^6 | α^7 | 1 | α | α^2 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^4 | 0 | α^4 | α^5 | α^6 | α^7 | 1 | α | α^2 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^5 | 0 | α^5 | α^6 | α^7 | 1 | α | α^2 | α^3 | α^4 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^6 | 0 | α^6 | α^7 | 1 | α | α^2 | α^3 | α^4 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| α^7 | 0 | α^7 | 1 | α | α^2 | α^3 | α^4 | α^5 | α^6 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Multiplicative inverse¶
As with prime fields, the division \(a(x) / b(x)\) is reformulated into \(a(x) b(x)^{-1}\). So, first we must compute the multiplicative inverse \(b^{-1}\) before continuing onto division.
The Extended Euclidean Algorithm,
which was used in prime fields on integers, can be used for extension fields on polynomials. Given two polynomials \(a(x)\) and
\(b(x)\), the Extended Euclidean Algorithm finds the polynomials \(s(x)\) and \(t(x)\) such that
\(a(x)s(x) + b(x)t(x) = \textrm{gcd}(a(x), b(x))\). This algorithm is implemented in egcd().
If \(a(x) = x + 1\) is a field element of \(\mathrm{GF}(3^2)\) and \(b(x) = f(x)\) is the irreducible polynomial, then \(s(x) = a^{-1}\) in \(\mathrm{GF}(3^2)\). Note, the GCD will always be \(1\) because \(f(x)\) is irreducible.
# Returns (gcd, s, t)
In [52]: galois.egcd(b_poly, f)
Out[52]: (Poly(1, GF(3)), Poly(2x + 2, GF(3)), Poly(1, GF(3)))
The galois library uses the Extended Euclidean Algorithm to compute multiplicative inverses (and division) in extension fields.
The inverse of \(x + 1\) in \(\mathrm{GF}(3^2)\) can be easily computed in the following way.
In [53]: b ** -1
Out[53]: GF(8, order=3^2)
In [54]: np.reciprocal(b)
Out[54]: GF(8, order=3^2)
In [55]: b ** -1
Out[55]: GF(2α + 2, order=3^2)
In [56]: np.reciprocal(b)
Out[56]: GF(2α + 2, order=3^2)
In [57]: b ** -1
Out[57]: GF(α^6, order=3^2)
In [58]: np.reciprocal(b)
Out[58]: GF(α^6, order=3^2)
Division¶
Now let’s return to division in finite fields. As mentioned earlier, \(a(x) / b(x)\) is equivalent to \(a(x) b(x)^{-1}\), and we have already learned multiplication and multiplicative inversion in finite fields.
Let’s compute \(a / b = (x + 2)(x + 1)^{-1}\) in \(\mathrm{GF}(3^2)\).
In [59]: _, b_inv_poly, _ = galois.egcd(b_poly, f)
In [60]: (a_poly * b_inv_poly) % f
Out[60]: Poly(2x, GF(3))
In [61]: a * b**-1
Out[61]: GF(6, order=3^2)
In [62]: a / b
Out[62]: GF(6, order=3^2)
In [63]: _, b_inv_poly, _ = galois.egcd(b_poly, f)
In [64]: (a_poly * b_inv_poly) % f
Out[64]: Poly(2x, GF(3))
In [65]: a * b**-1
Out[65]: GF(2α, order=3^2)
In [66]: a / b
Out[66]: GF(2α, order=3^2)
In [67]: _, b_inv_poly, _ = galois.egcd(b_poly, f)
In [68]: (a_poly * b_inv_poly) % f
Out[68]: Poly(2x, GF(3))
In [69]: a * b**-1
Out[69]: GF(α^5, order=3^2)
In [70]: a / b
Out[70]: GF(α^5, order=3^2)
Here is the division table for completeness. Notice that division is not defined for \(y = 0\).
In [71]: print(GF9.arithmetic_table("/"))
+-------+---+---+---+---+---+---+---+---+
| x / y | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+-------+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-------+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 5 | 8 | 3 | 7 | 6 | 4 |
+-------+---+---+---+---+---+---+---+---+
| 2 | 2 | 1 | 7 | 4 | 6 | 5 | 3 | 8 |
+-------+---+---+---+---+---+---+---+---+
| 3 | 3 | 6 | 1 | 5 | 4 | 2 | 8 | 7 |
+-------+---+---+---+---+---+---+---+---+
| 4 | 4 | 8 | 3 | 1 | 7 | 6 | 5 | 2 |
+-------+---+---+---+---+---+---+---+---+
| 5 | 5 | 7 | 8 | 6 | 1 | 4 | 2 | 3 |
+-------+---+---+---+---+---+---+---+---+
| 6 | 6 | 3 | 2 | 7 | 8 | 1 | 4 | 5 |
+-------+---+---+---+---+---+---+---+---+
| 7 | 7 | 5 | 4 | 3 | 2 | 8 | 1 | 6 |
+-------+---+---+---+---+---+---+---+---+
| 8 | 8 | 4 | 6 | 2 | 5 | 3 | 7 | 1 |
+-------+---+---+---+---+---+---+---+---+
In [72]: print(GF9.arithmetic_table("/"))
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| x / y | 1 | 2 | α | α + 1 | α + 2 | 2α | 2α + 1 | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 1 | 1 | 2 | α + 2 | 2α + 2 | α | 2α + 1 | 2α | α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2 | 2 | 1 | 2α + 1 | α + 1 | 2α | α + 2 | α | 2α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α | α | 2α | 1 | α + 2 | α + 1 | 2 | 2α + 2 | 2α + 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 1 | α + 1 | 2α + 2 | α | 1 | 2α + 1 | 2α | α + 2 | 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| α + 2 | α + 2 | 2α + 1 | 2α + 2 | 2α | 1 | α + 1 | 2 | α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α | 2α | α | 2 | 2α + 1 | 2α + 2 | 1 | α + 1 | α + 2 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 1 | 2α + 1 | α + 2 | α + 1 | α | 2 | 2α + 2 | 1 | 2α |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 2α + 2 | 2α + 2 | α + 1 | 2α | 2 | α + 2 | α | 2α + 1 | 1 |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+
In [73]: print(GF9.arithmetic_table("/"))
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| x / y | 1 | α | α^2 | α^3 | α^4 | α^5 | α^6 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 1 | α^7 | α^6 | α^5 | α^4 | α^3 | α^2 | α |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| α | α | 1 | α^7 | α^6 | α^5 | α^4 | α^3 | α^2 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| α^2 | α^2 | α | 1 | α^7 | α^6 | α^5 | α^4 | α^3 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| α^3 | α^3 | α^2 | α | 1 | α^7 | α^6 | α^5 | α^4 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| α^4 | α^4 | α^3 | α^2 | α | 1 | α^7 | α^6 | α^5 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| α^5 | α^5 | α^4 | α^3 | α^2 | α | 1 | α^7 | α^6 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| α^6 | α^6 | α^5 | α^4 | α^3 | α^2 | α | 1 | α^7 |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
| α^7 | α^7 | α^6 | α^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^m)\) is an element such that \(\mathrm{GF}(p^m) = \{0, 1, g, g^2, \dots, g^{p^m - 2}\}\). The non-zero elements \(\{1, g, g^2, \dots, g^{p^m - 2}\}\) form the cyclic multiplicative group \(\mathrm{GF}(p^m)^{\times}\). A primitive element has multiplicative order \(\textrm{ord}(g) = p^m - 1\).
A primitive element¶
In galois, a primitive element of a finite field is provided by the primitive_element
class property.
In [74]: print(GF9.properties)
Galois Field:
name: GF(3^2)
characteristic: 3
degree: 2
order: 9
irreducible_poly: x^2 + 2x + 2
is_primitive_poly: True
primitive_element: x
In [75]: g = GF9.primitive_element; g
Out[75]: GF(3, order=3^2)
In [76]: print(GF9.properties)
Galois Field:
name: GF(3^2)
characteristic: 3
degree: 2
order: 9
irreducible_poly: x^2 + 2x + 2
is_primitive_poly: True
primitive_element: x
In [77]: g = GF9.primitive_element; g
Out[77]: GF(α, order=3^2)
In [78]: print(GF9.properties)
Galois Field:
name: GF(3^2)
characteristic: 3
degree: 2
order: 9
irreducible_poly: x^2 + 2x + 2
is_primitive_poly: True
primitive_element: x
In [79]: g = GF9.primitive_element; g
Out[79]: GF(α, order=3^2)
The galois package allows you to easily display all powers of an element and their equivalent polynomial, vector, and integer
representations using repr_table().
Here is the representation table using the default generator \(g = x\). Notice its multiplicative order is \(p^m - 1\).
In [80]: g.multiplicative_order()
Out[80]: 8
In [81]: print(GF9.repr_table())
+-------+------------+--------+---------+
| Power | Polynomial | Vector | Integer |
+-------+------------+--------+---------+
| 0 | 0 | [0, 0] | 0 |
+-------+------------+--------+---------+
| x^0 | 1 | [0, 1] | 1 |
+-------+------------+--------+---------+
| x^1 | x | [1, 0] | 3 |
+-------+------------+--------+---------+
| x^2 | x + 1 | [1, 1] | 4 |
+-------+------------+--------+---------+
| x^3 | 2x + 1 | [2, 1] | 7 |
+-------+------------+--------+---------+
| x^4 | 2 | [0, 2] | 2 |
+-------+------------+--------+---------+
| x^5 | 2x | [2, 0] | 6 |
+-------+------------+--------+---------+
| x^6 | 2x + 2 | [2, 2] | 8 |
+-------+------------+--------+---------+
| x^7 | x + 2 | [1, 2] | 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 [82]: GF9.primitive_elements
Out[82]: GF([3, 5, 6, 7], order=3^2)
In [83]: g = GF9("2x + 1"); g
Out[83]: GF(7, order=3^2)
In [84]: GF9.primitive_elements
Out[84]: GF([ α, α + 2, 2α, 2α + 1], order=3^2)
In [85]: g = GF9("2x + 1"); g
Out[85]: GF(2α + 1, order=3^2)
In [86]: GF9.primitive_elements
Out[86]: GF([ α, α^7, α^5, α^3], order=3^2)
In [87]: g = GF9("2x + 1"); g
Out[87]: GF(α^3, order=3^2)
This means that \(x\), \(x + 2\), \(2x\), and \(2x + 1\) all generate the multiplicative group \(\mathrm{GF}(3^2)^\times\). We can examine this by viewing the representation table using different generators.
Here is the representation table using a different generator \(g = 2x + 1\). Notice it also has multiplicative order \(p^m - 1\).
In [88]: g.multiplicative_order()
Out[88]: 8
In [89]: print(GF9.repr_table(g))
+------------+------------+--------+---------+
| Power | Polynomial | Vector | Integer |
+------------+------------+--------+---------+
| 0 | 0 | [0, 0] | 0 |
+------------+------------+--------+---------+
| (2x + 1)^0 | 1 | [0, 1] | 1 |
+------------+------------+--------+---------+
| (2x + 1)^1 | 2x + 1 | [2, 1] | 7 |
+------------+------------+--------+---------+
| (2x + 1)^2 | 2x + 2 | [2, 2] | 8 |
+------------+------------+--------+---------+
| (2x + 1)^3 | x | [1, 0] | 3 |
+------------+------------+--------+---------+
| (2x + 1)^4 | 2 | [0, 2] | 2 |
+------------+------------+--------+---------+
| (2x + 1)^5 | x + 2 | [1, 2] | 5 |
+------------+------------+--------+---------+
| (2x + 1)^6 | x + 1 | [1, 1] | 4 |
+------------+------------+--------+---------+
| (2x + 1)^7 | 2x | [2, 0] | 6 |
+------------+------------+--------+---------+
Non-primitive elements¶
All other elements of the field cannot generate the multiplicative group. They have multiplicative orders less than \(p^m - 1\).
For example, the element \(e = x + 1\) is not a primitive element. It has \(\textrm{ord}(e) = 4\). Notice elements \(x\), \(x + 2\), \(2x\), and \(2x + 1\) are not represented by the powers of \(e\).
In [90]: e = GF9("x + 1"); e
Out[90]: GF(4, order=3^2)
In [91]: e = GF9("x + 1"); e
Out[91]: GF(α + 1, order=3^2)
In [92]: e = GF9("x + 1"); e
Out[92]: GF(α^2, order=3^2)
In [93]: e.multiplicative_order()
Out[93]: 4
In [94]: print(GF9.repr_table(e))
+-----------+------------+--------+---------+
| Power | Polynomial | Vector | Integer |
+-----------+------------+--------+---------+
| 0 | 0 | [0, 0] | 0 |
+-----------+------------+--------+---------+
| (x + 1)^0 | 1 | [0, 1] | 1 |
+-----------+------------+--------+---------+
| (x + 1)^1 | x + 1 | [1, 1] | 4 |
+-----------+------------+--------+---------+
| (x + 1)^2 | 2 | [0, 2] | 2 |
+-----------+------------+--------+---------+
| (x + 1)^3 | 2x + 2 | [2, 2] | 8 |
+-----------+------------+--------+---------+
| (x + 1)^4 | 1 | [0, 1] | 1 |
+-----------+------------+--------+---------+
| (x + 1)^5 | x + 1 | [1, 1] | 4 |
+-----------+------------+--------+---------+
| (x + 1)^6 | 2 | [0, 2] | 2 |
+-----------+------------+--------+---------+
| (x + 1)^7 | 2x + 2 | [2, 2] | 8 |
+-----------+------------+--------+---------+