Xrfgtjtk

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.