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!
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?