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.
 A: 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.
A: 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.
