How to find primitive elements in $\operatorname{GF}(9)$

Question

I have to find primitive elements of $\operatorname{GF}(9)$ in finite field. $p=3$, $k=2$, $q=9$.

Am I correct, I need minimal polynomials to be

• $x^2$

• $x^2 + 1$

• $x^2 + 2$

• $x^2 + x$

• $x^2 + x + 1$

• $x^2 + x + 2$

• $x^2 + 2x$

• $x^2 + 2x + 1$

• $x^2 + 2x + 2$

and primitive elements to be $α, ..., α^7$

Can I find roots and calculate the powers of $a^i$ for $x^2+x$, because this polynomial is irreducible ?

How can I get binary code of 2-parts?

And how can I get powers of $α^i$?

Answer 1

The multiplicative group $\mathbb F_{p^n}^*$ is known to be cyclic, and it has order $q-1$ where $q=p^n$. Hence, an element $a$ generates that cyclic group if:

1. $a^{q-1}=1$ and

2. $a^{(q-1)/t}\neq1$ for every prime divisor $t$ of $q-1$.

The first condition is always true if you realize $\mathbb F_{p^n}$ as $\mathbb F_{p^n}\simeq \mathbb F_p[x] / r(x)$ with a polynomial of degree $n$ that's irreducible over $\mathbb F_p$. (If 1. is not satisfied then that implies $r$ is not irreducible, which might be handy for practical purposes when searching for suitable $r$.)

In your case, the only prime divisor of $q-1=8$ is $2$, hence $a\in\mathbb F_9^*$ is primitive iff $a^4\neq1$.

In order to realize $\mathbb F_9^*$ by means of an irreducible polynomial $r(x)=c_2x^2+c_1x+c_0$, we may assume $c_2=1$ and $c_0\neq0$, and we have $1+c_1+c_0\neq0$ (because otherwise 1 would be a zero of $r$. The only remaining value we need to probe is $x=2=-1$ which must satisfy $p(2)\neq0$. Let's use $$r(x)=x^2+1$$ as it satisfies all three conditions. This polynomial is also very convenient because it's roots satisfy $x^{2m}=(-1)^m$. In the remainder, let $r(x)=0$.

Now let's try whether some values of $a$ satisfy condition 2. from above, e.g. $a=x$. Because $a^4=x^4=(-1)^2=1$, that particular $a$ is not primitive.

Try $a=x+1$: $a^2=x^2+2x+1=2x=-x$ thus $a^4=(-1)^2x^2=1\cdot(-1)\neq 1$. You got the idea...