Primitive polynomial of a Galois field

Question

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.

Answer 1

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.

Answer 2

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.