Intro to Galois Fields: Extension Fields
As discussed in the previous 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 can be mostly computed using integer arithmetic mod \(p\). In the case of prime power order, namely extension fields \(\mathrm{GF}(p^m)\), the finite field arithmetic is computed using polynomials over \(\mathrm{GF}(p)\) with degree less than \(m\).
Elements
The elements of the Galois field \(\mathrm{GF}(p^m)\) can be thought of as the integers \(\{0, 1, \dots, p^m - 1\}\), although their arithmetic doesn’t obey integer arithmetic. A more common interpretation is to view the elements of \(\mathrm{GF}(p^m)\) as polynomials over \(\mathrm{GF}(p)\) with degree less than \(m\), for instance \(a_{m-1}x^{m-1} + a_{m-2}x^{m-2} + \dots + a_1x^1 + a_0 \in \mathrm{GF}(p)[x]\).
For example, consider the finite field \(\mathrm{GF}(3^2)\). The order of the field is 9, so we know there are 9 elements. The only question is what to call each element and how to represent them.
In [1]: GF9 = galois.GF(3**2); GF9
Out[1]: <class 'numpy.ndarray over GF(3^2)'>
In [2]: print(GF9.properties)
GF(3^2):
characteristic: 3
degree: 2
order: 9
irreducible_poly: x^2 + 2x + 2
is_primitive_poly: True
primitive_element: x
In galois, the default element display mode is the integer representation. This is natural when storing and working with
integer numpy arrays. However, there are other representations and at times it may be useful to view the elements
in one of those representations.
In [3]: GF9.Elements()
Out[3]: GF([0, 1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
Below, we will view the representation table again to compare and contrast the different equivalent representations.
In [4]: 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 ║
╚═══════╧════════════╧════════╧═════════╝
As before, there are some elements whose powers generate the field; we’ll skip them for now. The main takeaway from this table is the equivalence of the integer representation and the polynomial (or vector) representation. In \(\mathrm{GF}(3^2)\), the element \(2\alpha + 1\) is a polynomial that can be thought of as \(2x + 1\) (we’ll explain why \(\alpha\) is used later). The conversion between the polynomial and integer representation is performed simply by substituting \(x = 3\) into the polynomial \(2*3 + 1 = 7\), using normal integer arithmetic.
With galois, we can represent a single Galois field element using GF9(int) or GF9(string).
# Create a single field element from its integer representation
In [5]: GF9(7)
Out[5]: GF(7, order=3^2)
# Create a single field element from its polynomial representation
In [6]: GF9("2x + 1")
Out[6]: GF(7, order=3^2)
# Create a single field element from its vector representation
In [7]: GF9.Vector([2,1])
Out[7]: GF(7, order=3^2)
In addition to scalars, these conversions work for arrays.
In [8]: GF9([4, 8, 7])
Out[8]: GF([4, 8, 7], order=3^2)
In [9]: GF9(["x + 1", "2x + 2", "2x + 1"])
Out[9]: GF([4, 8, 7], order=3^2)
In [10]: GF9.Vector([[1,1], [2,2], [2,1]])
Out[10]: GF([4, 8, 7], order=3^2)
Anytime you have a large array, you can easily view its elements in whichever mode is most illustrative.
In [11]: x = GF9.Elements(); x
Out[11]: GF([0, 1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
# Temporarily print x using the power representation
In [12]: with GF9.display("power"):
....: print(x)
....:
GF([0, 1, α^4, α, α^2, α^7, α^5, α^3, α^6], order=3^2)
# Permanently set the display mode to the polynomial representation
In [13]: GF9.display("poly"); x
Out[13]: GF([0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1, 2α + 2], order=3^2)
# Reset the display mode to the integer representation
In [14]: GF9.display(); x
Out[14]: GF([0, 1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
# Or convert the (10,) array of GF(p^m) elements to a (10,2) array of vectors over GF(p)
In [15]: x.vector()
Out[15]:
GF([[0, 0],
[0, 1],
[0, 2],
[1, 0],
[1, 1],
[1, 2],
[2, 0],
[2, 1],
[2, 2]], order=3)
Arithmetic mod p(x)
In prime fields \(\mathrm{GF}(p)\), integer arithmetic (addition, subtraction, and multiplication) was performed and then reduced modulo \(p\). In extension fields \(\mathrm{GF}(p^m)\), polynomial arithmetic (addition, subtraction, and multiplication) is performed over \(\mathrm{GF}(p)\) and then reduced by a polynomial \(p(x)\). This polynomial is called an irreducible polynomial because it cannot be factored over \(\mathrm{GF}(p)\) – an analogue of a prime number.
When constructing an extension field, if an explicit irreducible polynomial is not specified, a default is chosen. The default
polynomial is a Conway polynomial which is irreducible and primitive, see galois.conway_poly() for more information.
In [16]: p = GF9.irreducible_poly; p
Out[16]: Poly(x^2 + 2x + 2, GF(3))
In [17]: galois.is_irreducible(p)
Out[17]: True
# Explicit polynomial factorization returns itself as a multiplicity-1 factor
In [18]: galois.factors(p)
Out[18]: ([Poly(x^2 + 2x + 2, GF(3))], [1])
Polynomial addition and subtract never result in polynomials of larger degree, so it is unnecessary to reduce them
modulo \(p(x)\). Let’s try an example of addition. Suppose two field elements \(a = x + 2\) and \(b = x + 1\).
These polynomials add degree-wise in \(\mathrm{GF}(p)\). Relatively easily we can see that \(a + b = (1 + 1)x + (2 + 1) = 2x\). But we can use
galois and galois.Poly to confirm this.
In [19]: GF3 = galois.GF(3)
# Explicitly create a polynomial over GF(3) to represent a
In [20]: a = galois.Poly([1, 2], field=GF3); a
Out[20]: Poly(x + 2, GF(3))
In [21]: a.integer
Out[21]: 5
# Explicitly create a polynomial over GF(3) to represent b
In [22]: b = galois.Poly([1, 1], field=GF3); b
Out[22]: Poly(x + 1, GF(3))
In [23]: b.integer
Out[23]: 4
In [24]: c = a + b; c
Out[24]: Poly(2x, GF(3))
In [25]: c.integer
Out[25]: 6
We can do the equivalent calculation directly in the field \(\mathrm{GF}(3^2)\).
In [26]: a = GF9("x + 2"); a
Out[26]: GF(5, order=3^2)
In [27]: b = GF9("x + 1"); b
Out[27]: GF(4, order=3^2)
In [28]: c = a + b; c
Out[28]: GF(6, order=3^2)
# Or view the answer in polynomial form
In [29]: with GF9.display("poly"):
....: print(c)
....:
GF(2α, order=3^2)
From here, we can view the entire addition arithmetic table. And we can choose to view the elements in the integer representation or polynomial representation.
In [30]: 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 [31]: with GF9.display("poly"):
....: 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 ║
╚════════╩════════╧════════╧════════╧════════╧════════╧════════╧════════╧════════╧════════╝
Polynomial multiplication, however, often results in products of larger degree than the multiplicands. In this case, the result must be reduced modulo \(p(x)\).
Let’s use the same example from before with \(a = x + 2\) and \(b = x + 1\). To compute \(c = ab\), we need to multiply the polynomials \(c = (x + 2)(x + 1) = x^2 + 2\) in \(\mathrm{GF}(3)\). The issue is that \(x^2 + 2\) has degree-\(2\) and the elements of \(\mathrm{GF}(3^2)\) can have degree at most \(1\), hence the need to reduce modulo \(p(x)\). After remainder division, we see that \(c = ab\ \equiv x\ \textrm{mod}\ p\).
As before, let’s compute this polynomial product explicitly first.
# The irreducible polynomial for GF(3^2)
In [32]: p = GF9.irreducible_poly; p
Out[32]: Poly(x^2 + 2x + 2, GF(3))
# Explicitly create a polynomial over GF(3) to represent a
In [33]: a = galois.Poly([1, 2], field=GF3); a
Out[33]: Poly(x + 2, GF(3))
In [34]: a.integer
Out[34]: 5
# Explicitly create a polynomial over GF(3) to represent b
In [35]: b = galois.Poly([1, 1], field=GF3); b
Out[35]: Poly(x + 1, GF(3))
In [36]: b.integer
Out[36]: 4
In [37]: c = (a * b) % p; c
Out[37]: Poly(x, GF(3))
In [38]: c.integer
Out[38]: 3
And now we’ll compare that direct computation of this finite field multiplication is equivalent.
In [39]: a = GF9("x + 2"); a
Out[39]: GF(5, order=3^2)
In [40]: b = GF9("x + 1"); b
Out[40]: GF(4, order=3^2)
In [41]: c = a * b; c
Out[41]: GF(3, order=3^2)
# Or view the answer in polynomial form
In [42]: with GF9.display("poly"):
....: print(c)
....:
GF(α, order=3^2)
Now the entire multiplication table can be shown for completeness.
In [43]: with GF9.display("poly"):
....: 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 ║
╚════════╩════════╧════════╧════════╧════════╧════════╧════════╧════════╧════════╧════════╝
Division, as in \(\mathrm{GF}(p)\), is a little more difficult. Fortunately the Extended Euclidean Algorithm, which
was used in prime fields on integers, can be used for extension fields on polynomials. Given two polynomials \(a\)
and \(b\), the Extended Euclidean Algorithm finds the polynomials \(x\) and \(y\) such that
\(xa + yb = \textrm{gcd}(a, b)\). This algorithm is implemented in galois.egcd().
If \(a = x + 2\) is a field element of \(\mathrm{GF}(3^2)\) and \(b = p(x)\), the field’s irreducible polynomial, then \(x = a^{-1}\) in \(\mathrm{GF}(3^2)\). Note, the GCD will always be \(1\) because \(p(x)\) is irreducible.
In [44]: p = GF9.irreducible_poly; p
Out[44]: Poly(x^2 + 2x + 2, GF(3))
In [45]: a = galois.Poly([1, 2], field=GF3); a
Out[45]: Poly(x + 2, GF(3))
In [46]: gcd, x, y = galois.egcd(a, p); gcd, x, y
Out[46]: (Poly(1, GF(3)), Poly(x, GF(3)), Poly(2, GF(3)))
The claim is that \((x + 2)^{-1} = x\) in \(\mathrm{GF}(3^2)\) or, equivalently, \((x + 2)(x)\ \equiv 1\ \textrm{mod}\ p(x)\). This
can be easily verified with galois.
In [47]: (a * x) % p
Out[47]: Poly(1, GF(3))
galois performs all this arithmetic under the hood. With galois, performing finite field arithmetic
is as simple as invoking the appropriate numpy function or binary operator.
In [48]: a = GF9("x + 2"); a
Out[48]: GF(5, order=3^2)
In [49]: np.reciprocal(a)
Out[49]: GF(3, order=3^2)
In [50]: a ** -1
Out[50]: GF(3, order=3^2)
# Or view the answer in polynomial form
In [51]: with GF9.display("poly"):
....: print(a ** -1)
....:
GF(α, order=3^2)
And finally, for completeness, we’ll include the division table for \(\mathrm{GF}(3^2)\). Note, division is not defined for \(y = 0\).
In [52]: with GF9.display("poly"):
....: 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 ║
╚════════╩════════╧════════╧════════╧════════╧════════╧════════╧════════╧════════╝
Primitive elements
A property of finite fields is that some elements can produce the entire field by their powers. Namely, a primitive element \(g\) of \(\mathrm{GF}(p^m)\) is an element such that \(\mathrm{GF}(p^m) = \{0, g^0, g^1, \dots, g^{p^m - 1}\}\).
In galois, the primitive elements of an extension field can be found by the class attribute galois.FieldClass.primitive_element
and galois.FieldClass.primitive_elements.
# Switch to polynomial display mode
In [53]: GF9.display("poly");
In [54]: p = GF9.irreducible_poly; p
Out[54]: Poly(x^2 + 2x + 2, GF(3))
In [55]: GF9.primitive_element
Out[55]: GF(α, order=3^2)
In [56]: GF9.primitive_elements
Out[56]: GF([α, α + 2, 2α, 2α + 1], order=3^2)
This means that \(x\), \(x + 2\), \(2x\), and \(2x + 1\) can all generate the nonzero 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 the default generator \(g = x\).
In [57]: 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 ║
╚═══════╧════════════╧════════╧═════════╝
And here is the representation table using a different generator \(g = 2x + 1\).
In [58]: print(GF9.repr_table(GF9("2x + 1")))
╔════════════╤════════════╤════════╤═════════╗
║ 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 ║
╚════════════╧════════════╧════════╧═════════╝
All other elements cannot generate the multiplicative subgroup. Another way of putting that is that their multiplicative order is less than \(p^m - 1\). For example, the element \(e = x + 1\) has \(\textrm{ord}(e) = 4\). This can be seen because \(e^4 = 1\).
In [59]: print(GF9.repr_table(GF9("x + 1")))
╔═══════════╤════════════╤════════╤═════════╗
║ 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 ║
╚═══════════╧════════════╧════════╧═════════╝
Primitive polynomials
Some irreducible polynomials have special properties, these are primitive polynomial. A degree-\(m\) polynomial is primitive over \(\mathrm{GF}(p)\) if it has as a root that is a generator of \(\mathrm{GF}(p^m)\).
In galois, the default choice of irreducible polynomial is a Conway polynomial, which is also a
primitive polynomial. Consider the finite field \(\mathrm{GF}(2^4)\). The Conway polynomial for \(\mathrm{GF}(2^4)\)
is \(C_{2,4} = x^4 + x + 1\), which is irreducible and primitive.
In [60]: GF16 = galois.GF(2**4)
In [61]: print(GF16.properties)
GF(2^4):
characteristic: 2
degree: 4
order: 16
irreducible_poly: x^4 + x + 1
is_primitive_poly: True
primitive_element: x
Since \(p(x) = C_{2,4}\) is primitive, it has the primitive element of \(\mathrm{GF}(2^4)\) as a root.
In [62]: p = GF16.irreducible_poly; p
Out[62]: Poly(x^4 + x + 1, GF(2))
In [63]: galois.is_irreducible(p)
Out[63]: True
In [64]: galois.is_primitive(p)
Out[64]: True
# Evaluate the irreducible polynomial over GF(2^4) at the primitive element
In [65]: p(GF16.primitive_element, field=GF16)
Out[65]: GF(0, order=2^4)
Since the irreducible polynomial is primitive, we write the field elements in polynomial basis with indeterminate \(\alpha\) instead of \(x\), where \(\alpha\) represents the primitive element of \(\mathrm{GF}(p^m)\). For powers of \(\alpha\) less than 4, it can be seen that \(\alpha = x\), \(\alpha^2 = x^2\), and \(\alpha^3 = x^3\).
In [66]: print(GF16.repr_table())
╔═══════╤═══════════════════╤══════════════╤═════════╗
║ Power │ Polynomial │ Vector │ Integer ║
║═══════╪═══════════════════╪══════════════╪═════════║
║ 0 │ 0 │ [0, 0, 0, 0] │ 0 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^0 │ 1 │ [0, 0, 0, 1] │ 1 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^1 │ x │ [0, 0, 1, 0] │ 2 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^2 │ x^2 │ [0, 1, 0, 0] │ 4 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^3 │ x^3 │ [1, 0, 0, 0] │ 8 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^4 │ x + 1 │ [0, 0, 1, 1] │ 3 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^5 │ x^2 + x │ [0, 1, 1, 0] │ 6 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^6 │ x^3 + x^2 │ [1, 1, 0, 0] │ 12 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^7 │ x^3 + x + 1 │ [1, 0, 1, 1] │ 11 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^8 │ x^2 + 1 │ [0, 1, 0, 1] │ 5 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^9 │ x^3 + x │ [1, 0, 1, 0] │ 10 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^10 │ x^2 + x + 1 │ [0, 1, 1, 1] │ 7 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^11 │ x^3 + x^2 + x │ [1, 1, 1, 0] │ 14 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^12 │ x^3 + x^2 + x + 1 │ [1, 1, 1, 1] │ 15 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^13 │ x^3 + x^2 + 1 │ [1, 1, 0, 1] │ 13 ║
╟───────┼───────────────────┼──────────────┼─────────╢
║ x^14 │ x^3 + 1 │ [1, 0, 0, 1] │ 9 ║
╚═══════╧═══════════════════╧══════════════╧═════════╝
Extension fields do not need to be constructed from primitive polynomials, however. The polynomial \(p(x) = x^4 + x^3 + x^2 + x + 1\) is irreducible, but not primitive. This polynomial can define arithmetic in \(\mathrm{GF}(2^4)\). The two fields (the first defined by a primitive polynomial and the second defined by a non-primitive polynomial) are isomorphic to one another.
In [67]: p = galois.Poly.Degrees([4,3,2,1,0]); p
Out[67]: Poly(x^4 + x^3 + x^2 + x + 1, GF(2))
In [68]: galois.is_irreducible(p)
Out[68]: True
In [69]: galois.is_primitive(p)
Out[69]: False
In [70]: GF16_v2 = galois.GF(2**4, irreducible_poly=p)
In [71]: print(GF16_v2.properties)
GF(2^4):
characteristic: 2
degree: 4
order: 16
irreducible_poly: x^4 + x^3 + x^2 + x + 1
is_primitive_poly: False
primitive_element: x + 1
In [72]: with GF16_v2.display("poly"):
....: print(GF16_v2.primitive_element)
....:
GF(x + 1, order=2^4)
Notice the primitive element of \(\mathrm{GF}(2^4)\) with irreducible polynomial \(p(x) = x^4 + x^3 + x^2 + x + 1\) does not have \(x + 1\) as root in \(\mathrm{GF}(2^4)\).
# Evaluate the irreducible polynomial over GF(2^4) at the primitive element
In [73]: p(GF16_v2.primitive_element, field=GF16_v2)
Out[73]: GF(6, order=2^4)
As can be seen in the representation table, for powers of \(\alpha\) less than 4, \(\alpha \neq x\), \(\alpha^2 \neq x^2\), and \(\alpha^3 \neq x^3\). Therefore the polynomial indeterminate used is \(x\) to distinguish it from \(\alpha\), the primitive element.
In [74]: print(GF16_v2.repr_table())
╔════════════╤═══════════════════╤══════════════╤═════════╗
║ Power │ Polynomial │ Vector │ Integer ║
║════════════╪═══════════════════╪══════════════╪═════════║
║ 0 │ 0 │ [0, 0, 0, 0] │ 0 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^0 │ 1 │ [0, 0, 0, 1] │ 1 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^1 │ x + 1 │ [0, 0, 1, 1] │ 3 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^2 │ x^2 + 1 │ [0, 1, 0, 1] │ 5 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^3 │ x^3 + x^2 + x + 1 │ [1, 1, 1, 1] │ 15 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^4 │ x^3 + x^2 + x │ [1, 1, 1, 0] │ 14 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^5 │ x^3 + x^2 + 1 │ [1, 1, 0, 1] │ 13 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^6 │ x^3 │ [1, 0, 0, 0] │ 8 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^7 │ x^2 + x + 1 │ [0, 1, 1, 1] │ 7 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^8 │ x^3 + 1 │ [1, 0, 0, 1] │ 9 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^9 │ x^2 │ [0, 1, 0, 0] │ 4 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^10 │ x^3 + x^2 │ [1, 1, 0, 0] │ 12 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^11 │ x^3 + x + 1 │ [1, 0, 1, 1] │ 11 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^12 │ x │ [0, 0, 1, 0] │ 2 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^13 │ x^2 + x │ [0, 1, 1, 0] │ 6 ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^14 │ x^3 + x │ [1, 0, 1, 0] │ 10 ║
╚════════════╧═══════════════════╧══════════════╧═════════╝