1
$\begingroup$

I have $GF(2^3)$ field defined by $\Pi(x)=x^3+x+1$. From literature they say those are the minimal polynomial, but I can't understand the operative method to find them. Any explanation for a general method?

$$\begin{array}{lll} \textbf{Elem.} & \textbf{Polyn.} & \color{red}{\textbf{Minimal Polyn.}} \\ 0 & 0 & \color{red}{x} \\ \alpha^0 & 1 & \color{red}{x+1} \\ \alpha^1 & \alpha & \color{red}{x^3+x+1} \\ \alpha^2 & \alpha^2 & \color{red}{x^3+x+1} \\ \alpha^3 & \alpha+1 & \color{red}{x^3+x^2+1} \\ \alpha^4 & \alpha^2+\alpha & \color{red}{x^3+x+1} \\ \alpha^5 & \alpha^2+\alpha+1 & \color{red}{x^3 + x^2 + 1} \\ \alpha^6 & \alpha^2+1 & \color{red}{x^3 + x^2 + 1} \\ \end{array}$$

Note: I saw another post about minimal polynomial but there was no such method explained

$\endgroup$
  • 1
    $\begingroup$ For the field of eight elements you can use the fact that $\alpha,\alpha^2$ and $\alpha^4$ are Galois conjugates and hence share a minimal polynomial. The same applies to $\alpha^3,(\alpha^3)^2=\alpha^6$ and $(\alpha^6)^2=\alpha^5$. As $\alpha^6$ is the reciprocal of $\alpha$, the respective minimal polynomials are each others reciprocals as well. Note that $\alpha^5=1/\alpha^2$ and $\alpha^3=1/\alpha^4$ so the reciprocal relation holds for the entire class of conjugates. $\endgroup$ – Jyrki Lahtonen Dec 21 '18 at 8:16
  • 1
    $\begingroup$ For a method of sorts ... there are several. I outlined one here. A possibly simpler one is described here, but that works only when the element of interest generates the extension field. $\endgroup$ – Jyrki Lahtonen Dec 21 '18 at 8:20
  • $\begingroup$ Maybe I miss something, I can't obtain from your example the linear system (cit): " At this point we can set up a linear system for the unknowns $c_0,c_1,\cdots,c_5$ and find a solution of the system $$ c_0+c_1\beta+c_2\beta^2+c_3\beta^3+c_4\beta^4+c_5\beta^5=0 $$ by plugging in the values of the powers $\beta^i$ and then set the coefficients of all the powers of $\alpha$ to zero (the powers $1,\alpha,\cdots,\alpha^4$ are linearly independent (because $4<m=5$) so this is valid." $\endgroup$ – Alessar Dec 21 '18 at 12:44
  • $\begingroup$ @JyrkiLahtonen I understand now. Thank you so much for you great link!!!! $\endgroup$ – Alessar Dec 21 '18 at 14:53
2
$\begingroup$

The elements of $GF(8)$ are exactly the roots of the polynomial $X^8-X\in GF(2)[X]$. This polynomial decomposes into irreducible polynomials as follows, $$X^8-X = X(X+1)(X^3+X+1)(X^3+X^2+1).$$ If the field $GF(8)$ is given as $GF(2)[X]/\langle X^3+X+1\rangle$ and $\alpha$ is a zero of $X^3+X+1$, then (as stated above), $\alpha,\alpha^2,\alpha^4$ are the zeros of $X^3+X+1$ and $\alpha^3,(\alpha^3)^2=\alpha^6,((\alpha^3)^2)^2=\alpha^5$ are the zeros of $X^3+X^2+1$.

$\endgroup$
  • $\begingroup$ So, knowing the irriducible polynomial over $GF(8)$, I simply try plugging the $\alpha^i$ into one or another and the one who is the zero is it's minimal polynomial? $\endgroup$ – Alessar Dec 22 '18 at 8:29
  • $\begingroup$ Indeed, that's correct $\endgroup$ – Wuestenfux Dec 22 '18 at 8:35
  • $\begingroup$ And to find the irriducible polynomial over a given field, one must show that $p(0)=p(1)\equiv 1 \pmod p$ and that the polynomial has an odd number of factor, right? Because I think this is the tricky part of finding minimal polynomial $\endgroup$ – Alessar Dec 22 '18 at 8:39

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.