2
$\begingroup$

I'm trying to find the primitive elements of $GF(8),$ the minimal polynomials of all elements of $GF(8)$ and their roots, and calculate the powers of $\alpha^i$ for $x^3 + x + 1.$

If I did my math correct, I found the minimal polynomials to be $x, x + 1, x^3 + x + 1,$ and $x^3 + x^2 + 1,$ and the primitive elements to be $\alpha, \dots, \alpha^6 $

Would the powers of $\alpha^i$ as a polynomial (of degree at most two) be: $\alpha, \alpha^2, \alpha+ 1, \alpha^2 + \alpha, \alpha^2 + \alpha + 1,$ and $\alpha^2 + 1$?

Am I on the right track?

$\endgroup$
  • $\begingroup$ Snowball kindly gave you the list, and yours is correct (+1 to you both). See also here for examples of using this as well as a similar list for $GF(16)$. $\endgroup$ – Jyrki Lahtonen Oct 24 '14 at 19:40
3
$\begingroup$

Those are all correct. Here's everything presented in a table:

$$\begin{array}{lll} \textbf{element} & \textbf{reduced} & \textbf{min poly} \\ 0 & 0 & x \\ \alpha^0 & 1 & x+1 \\ \alpha^1 & \alpha & x^3+x+1 \\ \alpha^2 & \alpha^2 & x^3+x+1 \\ \alpha^3 & \alpha+1 & x^3+x^2+1 \\ \alpha^4 & \alpha^2+\alpha & x^3+x+1 \\ \alpha^5 & \alpha^2+\alpha+1 & x^3 + x^2 + 1 \\ \alpha^6 & \alpha^2+1 & x^3 + x^2 + 1 \\ \end{array}$$

$\endgroup$
  • $\begingroup$ I can't understand quite well the procedure with one can find the minimal polynomial; without creating a duplicate, can someone enlight this process? I know the properties below by Ken Duna, but I've difficulties anyway! $\endgroup$ – Alessar Dec 20 '18 at 15:33
1
$\begingroup$

What you have is correct. Some general facts that you can use to check that you have all of the polynomials are the following:

Let $p$ be prime and $q=p^k$.

$\textbf{Fact 1:}$ In $GF(q)$ the product of all monic irreducible polynomials of degree dividing $n$ is $x^{q^n}-x$.

$\textbf{Fact 2:}$ The minimal polynomial of any element of $GF(q)$ is a monic irreducible polynomial over $GF(p)$ whose degree divides $k$.

Set $p=2$, $k=3$. Then $q = 8$.

Using fact 2, we see that the minimal polynomial of any element of $GF(8)$ is a monic irreducible polynomial over $GF(2)$ whose degree is $1$ or $3$.

Using fact 1, we see that the product of all monic irreducible polynomials of degree $1$ or $3$ over $GF(2)$ is $x^8-x$.

You can check that the product of the set of polynomials you listed is $x^8-x$ over $GF(2)$.

$\endgroup$
  • $\begingroup$ This is a great source for finite fields which includes the facts I listed. $\endgroup$ – Ken Duna Jul 10 '16 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.