# Primitive polynomial of a Galois field

How can one check that a polynomial is primitive polynomial or not?

I have following polynomial $$f(x) = x^3 + x^2 + 1$$ and i want to know if i can use it to generate $$GF(2^3)$$.

The definition i have so far says:

The minimum polynomial of a primitive element is called primitive polynomial. What does it mean to have a minimum polynomial of primitive element?

It can be a very basic question but i can't find out how to control whether a polynomial is primitive or not. Any help would be great.

In $$GF(2)[x]$$ you have:

$$x^8-x= x(x-1)(x^3+x+1)(x^3+x^2+1)$$

and $$f(x)=x^3+x^2+1$$ is irreducible over $$GF(2)$$. To decide if it is a primitive polynomial, you need to know if it has a root in $$GF(2^3)$$ that generates the multiplicative subgroup of $$GF(2^3)$$.

The multiplicative subgroup of $$GF(2^3)$$ is a group of order $$7$$ which is a prime number. And in a group of order a prime number, the order of all elements except the identity element is the order of the group. As $$1$$ isn’t a root of $$f$$, the order in $$GF(2^3)$$ of a root of $$f$$ is equal to $$7$$.

That proves that $$f$$ is primitive.

With

$$\mu(x) = x^3 + x^2 + 1 \in GF(2)[x] = \Bbb Z_2[x], \tag 1$$

we note that $$\mu(x)$$, being a cubic, is reducible in $$GF(2)[x] = \Bbb Z_2[x]$$ if and only if it has a linear factor in $$\Bbb Z_2$$, that is, has a zero in this field; this follows from a simple degree argument: if

$$\mu(x) = \nu(x) \lambda(x), \; \nu(x), \lambda(x) \in GF(2)[x], \tag 2$$

then

$$3 = \deg \mu(x) = \deg \nu(x) + \deg \lambda(x); \; \deg \nu(x), \deg \lambda(x) \ge 1, \tag 3$$

from which we see that we cannot have

$$\deg \nu(x), \deg \lambda(x) \ge 2; \tag 4$$

we thus find that one of $$\nu(x)$$, $$\lambda(x)$$ is of degree one, and is a monic linear polynomial $$x - a$$; taking

$$\lambda(x) = x - a, \tag 5$$

we have

$$\mu(x) = (x - a)\nu(x), \tag 6$$

as asserted above. It follows that we can check the irreducibility of $$\mu(x)$$ by testing for a root in $$GF(2) = \Bbb Z_2$$; we easily see that neither $$0$$ nor $$1$$ satisfy $$\mu(x)$$, hence it is irreducible in $$\Bbb Z_2[x]$$; thus, the principal ideal

$$(\mu(x)) \subset GF(2)[x] \tag 7$$

is maximal, and

$$GF(2)[x]/(\mu(x)) \tag 8$$

is a field. It is well known that

$$[GF(2)[x]/(\mu(x)):GF(2)] = \deg \mu(x) = 3, \tag 9$$

from which we may infer that

$$GF(2)[x]/(\mu(x)) \cong GF(2^3), \tag{10}$$

since, up to isomorphism, $$GF(2^3)$$ is the only field of order $$2^3 = 8$$.

Now the elements of $$GF(2)[x]/(\mu(x))$$ are cosets of the ideal $$(\mu(x))$$ in $$GF(2)[x]$$; for

$$\rho(x) \in GF(2)[x] \tag{11}$$

we let

$$\overline{\rho(x)} = \rho(x) + (\mu(x)); \tag{12}$$

then

$$\bar 0 = 0 + (\mu(x)) = \mu(x), \; \bar 1 = 1 + (\mu(x)),$$ $$\bar x = x + (\mu(x)), \; \bar x^2 = x^2 + (\mu(x)), \; \text{and so forth}, \tag{13}$$

and we have

$$\bar x^3 + \bar x^2 + \bar 1 = x^3 + x^2 + 1 + (\mu(x)) = \mu(x) + (\mu(x)) = \mu(x) = \bar 0 + (\mu(x)), \tag{14}$$

that is,

$$\bar x^3 + \bar x^2 + \bar 1 = \bar 0 \tag{15}$$

in $$GF(2)[x]/(\mu(x)) = \Bbb Z_2[x]/(\mu(x))$$.

We show by direct calculation that $$\bar x$$ is a primitive element in the field $$GF(2)[x] / (\mu(x))$$; to do so, we observe that in accord with (10) $$GF(2)[x]/(\mu(x))$$ has $$8$$ elements, whence the multiplicative group $$(GF(2)[x]/(\mu(x)))^\times$$ is of order $$7$$, hence cyclic. By virtue of (15), we compute the powers of $$\bar x$$, starting with $$\bar x^0 = \bar 1$$, they are listed below:

$$\bar x^0 = \bar 1; \tag{16}$$

$$\bar x^1 = \bar x; \tag{17}$$

$$\bar x^2 = (\bar x)^2 = \bar x \bar x; \tag{18}$$

from this point on we may invoke (15) to reduce powers of $$\bar x$$ greater than the second:

$$\bar x^3 = \bar x^2 + \bar 1; \tag{19}$$

$$\bar x^4 = \bar x \bar x^3 = \bar x (\bar x^2 + 1) = \bar x^3 + \bar x = \bar x^2 + \bar x + \bar 1; \tag{20}$$

$$\bar x^5 = \bar x \bar x^4 = \bar x(\bar x^2 + \bar x + \bar 1) = \bar x^3 + \bar x^2 + \bar x = \bar x + \bar 1; \tag{21}$$

$$\bar x^6 = \bar x \bar x^5 = \bar x(\bar x + \bar 1) = \bar x^2 + \bar x; \tag{22}$$

$$\bar x^7 = \bar x(\bar x^2 + \bar x) = \bar x^3 + \bar x^2 = \bar 1 = \bar x^0; \tag{23}$$

from (16)-(23) we see that $$\bar x$$ generates each of the seven elements of $$(GF(2)[x]/(\mu(x)))^\times$$; thus it is a primitive element of this field. Then the polynomial $$x^3 + x^2 + 1 \in GF(2)[x]$$, being monic and irreducible, must be the minimal polynomial of $$\bar x$$ (this follows from the fact that the minimal polynomial is irreducible and divides any polynomial of which $$\bar x$$ is a root; but we have seen $$x^3 + x^2 + 1$$ is irreducible, so . . ), and it follows by definition that $$\mu(x)$$ is a primitive polynomial for $$GF(2)/(\mu(x)) \cong GF(2^3)$$.

It also is apparent from what we have said that we can use the polynomial $$\mu(x) = x^3 + x^2 + 1$$ to "generate" $$GF(2^3)$$, we simply form the quotient ring $$GF(2)[x]/(\mu(x))$$ as in (10).

The preceding discussion shows that $$\bar x = x + (\mu(x))$$ is a primitive element more or less by brute force, showing that $$\vert \bar x \vert = 7$$ by systematically evaluating $$\bar x^k$$, $$0 \le k \le 7$$; though the results form an engaging pattern which can help us better understand finite fields and their primitive elements, it is impractical to execute such a method manually except for polynomials of relatively low degree; obviously, high-speed digital computers can vastly extend the feasible range of such computations. Of course, having at one's disposal a lot of nice theorems pertaining to the issue can help a lot, but I my knowledge of such is far from encyclopedic. That being the case, the only way I know to find candidate primitive elements and their corresponding polynomials and just check things out; obviously, observations such as those made by mathcounterexamples.net in his/her answer are helpful in this regard.