# 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, repr="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, repr="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


Info

In this tutorial, we suggest using the polynomial representation to display the elements. 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: Aug 06, 2023