Verifying if a given polynomial is primitive polynomial

Question

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 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. — Jyrki Lahtonen, Jan 27, 2019 at 19:34

Robert Lewis · Accepted Answer · 2019-01-27 04:50:13Z

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!

1 Answer 1