Simpler method to show $k(x)$ is NOT a primitive irreducible polynomial? Let $k(x) = x^2+2x+2$ be under $\mathbb Z_{11}[x]$. Determine if $k(x)$ is irreducible, and if so, determine if it is primitive.
Ok, I showed that $k(x)$ is irreducible since it it a quadratic and has no linear factors.
A field constructed with $k(x)$ would have order $11^2=121$...and so the multiplicative group would have $120$ elements. If $x$ generates this group under multiplication modulo $k(x)$, then I would know that $k(x)$ is primitive. However, I would have to calculate $x^1,x^2,...,x^{120}$ to show this...
I figured that it would be ridiculous for a question like this to result in $k(x)$ being primitive, but what if it were? Would I really have to calculate $x^1,x^2,...,x^{120}$ in order to demonstrate this? Is there a much more efficient way of solving a problem like this?
 A: A quadratic polynomial $k(x)\in\Bbb{Z}_{11}[x]$ is primitive, iff the (multiplicative) order of the coset
$$
\alpha=x+\langle k(x)\rangle
$$
in the field $\Bbb{Z}_{11}[x]/\langle k(x)\rangle=\Bbb{F}_{121}$ is $120$. By Lagrange's theorem the order is always a factor of $120$. Thus it is one of $\{1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120\}$. To speed up checking you can furthermore make the  observation that if $\alpha^{120/p}\neq1$ for all prime factors $p$ of $120$ (s0 $p=2,3$ or $5$), then the order has to be maximal, i.e. $\alpha$ is a primitive element (or $k(x)$ is a primitive polynomial). Of course, it may turn out that $\alpha$ is not primitive, in which case you will see evidence of this at some point.
In this task square-and-multiply is your friend. Do remember to use the equation
$$
k(\alpha)=0\Longleftrightarrow\alpha^2=-(2\alpha+2)=9\alpha+9
$$
in each step.
For example
$$
\begin{array}{rll}
\alpha^2&=&=-(2\alpha+2)\\
\alpha^4&=(\alpha^2)^2=(2\alpha+2)^2=4\alpha^2+8\alpha+4&=7
\end{array}
$$
I stop here, because we see that something slightly unexpected happened: $\alpha^4$ belongs to the prime field $\Bbb{Z}_{11}$. At this point I reveal that you can answer the question about primitivity simply by calculating the order of $7$ in the prime field. Leaving that to you!
With 20/20 hindsight we can see that the result about $\alpha^4$ is a consequence of the factorization (in $\Bbb{Z}_{11}[x]$ or actually already in $\Bbb{Z}[x]$)
$$
x^4+4=(x^4+4x^2+4)-4x^2=(x^2+2)^2-(2x)^2=(x^2+2x+2)(x^2-2x+2)
$$
showing that $k(x)$ is a factor of $x^4+4=x^4-7$.
