Using a Generator

Using a Generator

An equivalent technique for defining a finite field of the form GF(2ⁿ) using the same irreducible polynomial, is sometimes more convenient. To begin, we need two definitions: A generator g of a finite field F of order q (contains q elements) is an element whose first q 1 powers generate all the nonzero elements of F. That is, the elements of F consist of 0, g⁰, g¹,..., g^q2. Consider a field F defined by a polynomial f(x). An element b contained in F is called a root of the polynomial if f(b) = 0. Finally, it can be shown that a root g of an irreducible polynomial is a generator of the finite field defined on that polynomial.

Let us consider the finite field GF(23), defined over the irreducible polynomial x3 + x + 1, discussed previously. Thus, the generator g must satisfy f(x) = g3 + g + 1 = 0. Keep in mind, as discussed previously, that we need not find a numerical solution to this equality. Rather, we deal with polynomial arithmetic in which arithmetic on the coefficients is performed modulo 2. Therefore, the solution to the preceding equality is g3 = g 1 = g + 1. We now show that g in fact generates all of the polynomials of degree less than 3. We have the following: g4 = g(g3) = g(g + 1) = g2 + g g5 = g(g4) = g(g2 + g) = g3 + g2 = g2 + g + 1 g6 = g(g5) = g(g2 + g + 1) = g3 + g2 + g = g2 + g + g + 1 = g2 + 1 g7 = g(g6) = g(g2 + 1) = g3 + g = g + g + 1 = 1 = g0 We see that the powers of g generate all the nonzero polynomials in GF(23). Also, it should be clear that gk = gk mod 7 for any integer k. Table 4.8 shows the power representation, as well as the polynomial and binary representations.

Table 4.8. Generator for GF(2³) using x³ + x + 1

Power Representation	Polynomial Representation	Binary Representation	Decimal (Hex) Representation
0	0	000	0
g0 ( = g7)	1	001	1
g1	g	010	2
g2	g2	100	4
g3	g + 1	011	3
g4	g2 + g	110	6
g5	g2 + g + 1	111	7
g6	g2 + 1	101	5

This power representation makes multiplication easy. To multiply in the power notation, add exponents modulo 7. For example, g⁴ x g⁶ = g^{(10 mod 7)} = g³ = g + 1. The same result is achieved using polynomial arithmetic, as follows: we have g⁴ = g² + g and g⁶ = g² + 1. Then, (g² + g) x (g² + 1) = g⁴ + g³ + g² + 1. Next, we need to determine (g⁴ + g³ + g² + 1) mod (g³ + g + 1) by division: