How to find minimal polynomial for an element in $\mbox{GF}(2^m)$?

Question

I'm new to this Finite field theory. Someone please explain how minimal polynomials are generated for each element in GF(2^m). I searched in the website but I'm not getting any clue.

Answer 1

This isn't too difficult because we only need methods from linear algebra. Let me do an example. I pick the field $GF(2^5)$ because for smaller fields I know the answer by heart, and I would fall back on ad hoc tricks rather than the general method.

Let $\alpha$ be a zero of the irreducible polynomial $x^5+x^2+1$. The task I assign to myself is to find the minimal polynomial of $\beta=\alpha^3$. From general theory we know that the minimal polynomial of $\beta$ has degree at most five (actually we can immediately see that it will be exactly five, but I try to avoid special knowledge here). So let's compute the powers $\beta^i, i\le 5$: $$ \begin{aligned} \beta^0&=&&=1,\\ \beta^1&=&&=\alpha^3,\\ \beta^2&=\alpha^6=\alpha\cdot\alpha^5=\alpha(\alpha^2+1)&&=\alpha^3+\alpha,\\ \beta^3&=\alpha^3(\alpha^3+\alpha)=\alpha^6+\alpha^4&&=\alpha^4+\alpha^3+\alpha,\\ \beta^4&=\alpha^7+\alpha^6+\alpha^4=\alpha^6+\alpha^2&&=\alpha^3+\alpha^2+\alpha,\\ \beta^5&=\alpha^6+\alpha^5+\alpha^4&&=\alpha^4+\alpha^3+\alpha^2+\alpha+1. \end{aligned} $$ 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. We get $$ \left\{\begin{array}{lcl} c_0+c_5&=&0,\\ c_2+c_3+c_4+c_5&=&0,\\ c_4+c_5&=&0,\\ c_1+c_2+c_3+c_4+c_5&=&0,\\ c_3+c_5&=&0. \end{array}\right. $$

Note: One term was missing from the second equation. Fixing the answer as well.

This is an underdetermined homogeneous system, so it has non-trivial solutions. The lowest degree one gives the minimal polynomial (if the solution space has dimension $>1$ then you set undetermined coefficients to zero starting from the highest). I am sure you learned to handle these in linear algebra. So I go ad hoc at this point, and "guess" that $c_5=1$. The equations involving only two unknowns then immediately yield $c_0=c_3=c_4=1$. The remaining equations then imply $c_2=1$ and $c_1=0$. This means that $\beta$ satisfies the equation $$ 1+\beta^2+\beta^3+\beta^4+\beta^5=0, $$ and its minimal polynomial is then $$ m(\beta,x)=m_3(x)=1+x^2+x^3+x^4+x^5. $$