# How to find minimal polynomial in $GF(2^3)$

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

• 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. – Jyrki Lahtonen Dec 21 '18 at 8:16
• 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. – Jyrki Lahtonen Dec 21 '18 at 8:20
• 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." – Alessar Dec 21 '18 at 12:44
• @JyrkiLahtonen I understand now. Thank you so much for you great link!!!! – Alessar Dec 21 '18 at 14:53

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$$.
• 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? – Alessar Dec 22 '18 at 8:29
• 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 – Alessar Dec 22 '18 at 8:39