Finding a primitive element in a field with 27 elements.

Question

I am trying to construct a field with 27 elements, and find a primitive element in that field. I considered the irreducible polynomial $f(x)=x^3+2x+1$ over $\mathbb{Z}_3[x]$. Then I considered $$\mathbb{Z}_3[x]/\langle f\rangle.$$ This is a field with $3^{\deg f}=3^3=27$ elements. I know that the unique elements of this field are given by $$\{a_0+a_1t+a_2t^2:a_i\in\mathbb{Z}_3\}$$ where $t=x+\langle f\rangle$. Now my question is, what is an efficient way (for beginners) to find a primitive element of this field? One could argue that it suffices to find an element $u\in\mathbb{Z}_3[x]/\langle f\rangle$ with $\text{ord}(u)\neq 1,2,13$, but finding such a $u$ is computationally tedious (at least to me). Any comments or advice appreciated.

Answer 1

$1$ has order $1$ and $2$ has order $2$. Any other (non-zero) element has order $13$ or $26$. Take an arbitrary element, like $t$, and calculate $t^{13}$ (for instance by repeated squaring: find $t^3$, then square that twice to get $t^{12}$, then multiply by $t$; this is much faster than multiplying $t$ by itself $13$ times).

If it turns out that $t^{13}=2=-1$, then you're done. If $t^{13}=1$, then $-t=2t$ has order $26$.

Answer 2

From Arthurs answer we know that just guessing an element $at^2+bt+c$, it will likely be primitive. We have to choose at least one of $a$ and $b$ non-zero, so trying $t$ itself first is a good start. I wanted to add how the computation reduces to taking powers of matrices, i.e., linear algebra.

Identifying a polynomial $at^2+bt+c\in\mathbb Z_3[x]/\langle f\rangle$ with the vector $(a,b,c)^T\in\mathbb Z_3^3$, the multiplicative action of $t$ is given by the matrix $$ Z = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 2 & 0 & 0 \end{pmatrix}. $$ This is obtained from $t(at^2+bt+c) = bt^2 + (a+c)t + 2a$.

Obviously $Z^2\neq I$, since $t^2\neq 1$ and using your favorite method of computing powers of matrices you get $Z^{13} = 2I \neq I$ as well. Hence $t$ is a primitive element in $\mathbb Z_3[x]/\langle f\rangle$.

If this didn't work out, you could now try other matrices $aZ^2+bZ+cI$ and compute their powers.