# 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)

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    |
+-----------+------------+--------+---------+

Last update: May 18, 2022