# Verifying if a given polynomial is primitive polynomial

Given a polynomial: $$f(x) = x^2 + 2x + 2$$ over $$GF(3)$$. I want to know if i can use it to construct $$GF(3^2)$$.

My approach:

• This equation satisfies first condition: A primitive polynomial is irreducible.
• The second condition i'm trying to confirm is that i can use it generate $$GF(3^2)$$.

$$\alpha^2 + 2\alpha + 2 \rightarrow \alpha^2 = \alpha + 1$$.

• $$\alpha^1 = \alpha$$

• $$\alpha^2 = \alpha+1$$

• $$\alpha^3 = \alpha*\alpha^2 \rightarrow1 + 2\alpha$$

• $$\alpha^4 = 2$$

• $$\alpha^5 = 2\alpha$$

• $$\alpha^6 = \alpha+2$$

• $$\alpha^7 = 1$$

Now Here $$\alpha^8$$ should be equal to $$1$$ instead of $$\alpha^7 .$$

• $$\alpha^8 = \alpha$$

What i am doing wrong , any help would be great.

• You made an error at $\alpha^6$. See my answer. Cheers! Jan 27, 2019 at 4:59
• You simply skipped $\alpha^6$. You correctly found out that $\alpha^4=2=-1$ is in the prime field. From this it follows that for all $i$ we have $\alpha^{4+i}=-\alpha^i$ (or $=2\alpha^i$ if you prefer that). So you should have $\alpha^6=2\alpha^2=2\alpha+2$, and only $\alpha^7=2\alpha^3=\alpha+2$. Undoubtedly you multiplied by $\alpha$ twice at that point, and forgot to record the result. Anyway, once you get back to the prime field you can use that to check the rest as above. Jan 27, 2019 at 19:34

It strikes me that our OP Khan Saab's calculations of the powers of $$\alpha$$ are OK through $$\alpha^5$$, but there is an error in $$\alpha^6$$. With

$$\alpha^2 = \alpha + 1, \tag 1$$

we have, correctly,

$$\alpha^5 = 2 \alpha; \tag 2$$

then

$$\alpha^6 = 2 \alpha^2 = 2 \alpha + 2, \tag 3$$

not $$\alpha^6 = \alpha + 2$$!

Continuing:

$$\alpha^7 = 2\alpha^2 + 2\alpha = 2(\alpha + 1) + 2\alpha = \alpha + 2; \tag 4$$

$$\alpha^8 = \alpha^2 + 2\alpha = \alpha + 1 + 2\alpha = 1! \tag 5$$

easy, you know the way it's supposed to be!