convert from polynomial to normal base in GF(2^5) I want to convert between the polynomial (standard) base to a type II optimal normal base.
for example take the field GF($2^5$) with the irreducible polynomal $p(x) = x^5+x^4+x^3+x+1$. In polynomial base I have an element represented as $a_0\alpha^0+a_1\alpha^2 + ... + a_4\alpha^4$, in normal base as $b_0\alpha^1 + b_1\alpha^2 + b_2\alpha^4 ... + b_4\alpha^{16}$.
So I wanted to calculate the conversion matrix $M$ satisfying the equation $a = M * b$, where $a$ and $b$ are vectors of the coefficients $a_0, a_1 ... $.
I thought that the columms of $M$ were the representation of the elements $\alpha, \alpha^2, \alpha^4, ..., \alpha^{16}$ mod $p(x)$. So my matrix $M$ was the following.
$$ M = \pmatrix{0 & 0 & 0 & 1 &0 \\ 1 &0 &0 &1 &0 \\ 0 &1 &0 &1 &0 \\ 0 &0 &0 &1 &1 \\ 0 &0 &1 &0 &1 }$$
To convert back I used the inverse of $M$. However as it turned out the conversion is not working properly. I tried to verify it by taking to random elements $c, d$ and multiplying it in the polynomial base and converting the result to normal base and comparing it to the result of representations of $c,d$ in normal base multiplied with a normal base multiplier. The multiplier are working correctly, they were used before. Sometimes I get the same result, sometimes I don't. 
Maybe my mistake is to assume that $\alpha$ is the same for both bases?
I hope you can understand my text as I am not used to mathematic formalism.
Thank you!
 A: This is somewhat speculative, because I don't trust my memory 100% about the structure of an optimal normal basis in this case (and you didn't describe it either).
I make the assumption that an optimal normal basis is constructed as follows. Let $\beta$ be a primitive eleventh root of unity. Then $\beta$ generates a normal basis for $GF(2^{10})$. The element $\alpha$ is then gotten as the relative trace of $\beta$:
$$
\alpha=\beta+\beta^{32}=\beta+\beta^{-1}.
$$
As 
$$\alpha^5=\alpha^4\alpha=(\beta^4+\beta^{-4})(\beta+\beta^{-1})=
\beta^5+\beta^3+\beta^{-3}+\beta^{-5}
$$
we easily see that
$$
\alpha^5+\alpha^4+\alpha^2+\alpha+1=\sum_{k=-5}^5\beta^k=0.
$$
Thus the minimal polynomial of this $\alpha$ is $r(x)=x^5+x^4+x^2+x+1$, i.e. the reciprocal of your $p(x)$.
To check that that we are talking about the same normal basis let us calculate the multiplication table of this one. So let's denote $\gamma_j=\alpha^{2^j}$ for $j=0,1,2,3,4$. Keeping in mind that $\beta^{11}=1$ we get
$$
\begin{aligned}
\gamma_0&=\beta+\beta^{-1}\\
\gamma_1&=\beta^2+\beta^{-2}\\
\gamma_2&=\beta^4+\beta^{-4}\\
\gamma_3&=\beta^8+\beta^{-8}=\beta^{-3}+\beta^3\\
\gamma_4&=\beta^{16}+\beta^{-16}=\beta^5+\beta^{-5}.
\end{aligned}
$$
It suffices to find the effect of multiplication by $\gamma_0$
as the others are gotten by shifting cyclically. The rule is
$$
(\beta+\beta^{-1})(\beta^k+\beta^{-k})=(\beta^{k+1}+\beta^{-(k+1)})+
(\beta^{k-1}+\beta^{-(k-1)}).
$$
Thus
$$
\begin{aligned}
\gamma_0\cdot\gamma_0&=\gamma_1,\\
\gamma_0\cdot\gamma_1&=\gamma_0+\gamma_3,\\
\gamma_0\cdot\gamma_2&=\gamma_3+\gamma_4,\\
\gamma_0\cdot\gamma_3&=\gamma_1+\gamma_2,\\
\gamma_0\cdot\gamma_4&=\gamma_2+\gamma_4.
\end{aligned}
$$
We got the hoped for $9=2\cdot5-1$ terms, so this normal basis is an optimal one.
In terms of the monomial basis given by $\alpha$, the elements of this normal basis are:
$$
\begin{aligned}
\gamma_0&=\alpha,\\
\gamma_1&=\alpha^2,\\
\gamma_2&=\alpha^4,\\
\gamma_3&=\alpha^3+\alpha,\\
\gamma_4&=\alpha^5+\alpha^3+\alpha=\alpha^4+\alpha^3+\alpha^2+1.
\end{aligned}
$$
Can you try again with these, and report back?
A: For the normal basis, you usually (always?) need to base it on an element $\beta$ that is not $\alpha$.  For your field, you can use
$\beta = \alpha^3$
basis vector: $b_0\beta^1 + b_1\beta^2 + b_2\beta^4 + b_3\beta^8 + b_4\beta^{16} $
