Let $\mathbb F_9$ be a finite field of size $9$ obtained via the irreducible polynomial $x^2 + 1$ over the base field $\mathbb F_3$.
- How can you find a primitive element?
- Make a list of the elements of $\mathbb F_9$ together with a primitive element and all the powers of the primitive element.
Best Answer
Let $\alpha$ be a root of $f = x^2 + 1$. You see immediately that this has period $4$ in $F_9^*$, so $\alpha$ is not a primitive element. However you know that $F_9^*$ is cyclic of order $8$, and thus $\langle \alpha \rangle$ is the unique subgroup of order $4$.
So take any $\beta \notin \langle \alpha \rangle$, and this will be primitive. For instance, take $\beta = \alpha + 1$. In computing the powers, just use $\alpha^2 = -1$. (Of course you mean computing the powers in the form $c + d \beta = (c+1) + d \alpha$, for $c, d \in F_3$.)
You can also note that the minimal polynomial of $\beta$ over $F_3$ is $g = (x -1)^2 + 1 = x^2 + x -1$, so that $\beta^2 + \beta - 1 = 0$. So you can use the relations $\beta^{i+2} = - \beta^{i+1} + \beta^{i}$ to quickly compute the powers of $\beta$.