How to find minimal polynomial for an element in $\mbox{GF}(2^m)$? 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.
 A: The conjugates of an element $\alpha$ of GF[$2^k$] are $\{\alpha^{(2^i)},\;i\geq 0 \}$.
This set contains at most $k$ distinct elements-- let them be $\beta_1,\ldots ,\beta_j$.  The minimal polynomial is
$$
p_\alpha(x)=\prod_{i=1}^j (x-\beta_i).
$$
A: 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.
$$
