<s>[INST] Finding element in binary representation of $GF(2^6)$ I got the following task:
Let $F = GF(2^6
)$ be K[x] modulo the primitive polynomial $h(x) = 1 +x
^2 +x
^3 +x
^5 +x
^6$
, and let $\alpha$ be the
class of x. I have a table with the binary representation of the elements of $GF(2^6
) = \{0; 1; \alpha^1; \alpha^2
; ...; \alpha^{62}\}$.
Is there a quicker way to check $\alpha^{52}$ than performing a long division of $x^{52}$ by $h(x)$ ?
It has $2^6$ elements so after $\alpha^{62}$ it will be back to 1 again, but maybe there is some trick to find it faster rather than performing such a long division?
I have also $\alpha^{13}$ so it's $\alpha^{13^4}$, but no idea how to use it
 [/INST] You say you have $\alpha^{13}$, so you can substitute suitable values into $\alpha^{13} = b_0 + b_1 \alpha + \ldots + b_5 \alpha^5$. Then $$\begin{eqnarray}\alpha^{26} & = & (\alpha^{13})^2 \\
& = &(b_0 + b_1 \alpha + \ldots + b_5 \alpha^5)^2 \\
& = &b_0 + b_1\alpha^2 + \ldots + b_5 \alpha^{10}
\end{eqnarray}$$
where the cross-terms cancel and so do the squares of the coefficients, because we're in characteristic $2$.
But we have $\alpha^6 = 1 + \alpha^2 + \alpha^3 + \alpha^5$, whence $\alpha^8 = 1 + \alpha$ and $\alpha^{10} = \alpha^2 + \alpha^3$. So
$$\begin{eqnarray}
\alpha^{26} & = & b_0 + b_1\alpha^2 + b_2\alpha^4 + b_3(1 + \alpha^2 + \alpha^3 + \alpha^5) + b_4(1 + \alpha) + b_5 (\alpha^2 + \alpha^3) \\
 & = & (b_0+b_3+b_4) + (b_4)\alpha + (b_1+b_3+b_5)\alpha^2 + (b_3+b_5)\alpha^3 + (b_2)\alpha^4 + (b_3)\alpha^5
\end{eqnarray}$$
Repeat for $\alpha^{52}$.
PS Minor nitpick: $2^6-1=63$, not $62$.
</s>