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

Solutions Collecting From Web of "Finding element in binary representation of $GF(2^6)$"

If you know the representation of $\alpha^{13}$ as a
polynomial $a(x) \in \mathbb F_2[x]$ of degree $5$ or less, then the representation of
$\alpha^{52} = (\alpha^{13})^4$ (not $\alpha^{13^4}$ the way you have
written it) is just
$$[a(x)]^4 \bmod h(x) = \left(\sum_{i=0}^5 a_i x^i\right)^4 \bmod h(x)= \sum_{i=0}^5 a_i x^{4i}
\bmod h(x).$$
Reducing a degree-$20$ polynomial modulo $h(x)$ is faster than reducing
a degree-$52$ polynomial.

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$.

The trick of using negative powers (in addition to Freshman’s dream as in Dilip’s answer) occasionally helps. Here we observe that $\alpha^{52}=\alpha^{-11}$.

Starting from the equation
$$1+\alpha^2+\alpha^3+\alpha^5+\alpha^6=0\qquad(*)$$
we get
$$
\begin{aligned}
\alpha^{-1}&=\alpha+\alpha^2+\alpha^4+\alpha^5,\\
\alpha^{-2}&=1+\alpha+\alpha^3+\alpha^4,\\
\alpha^{-3}&=\alpha^{-1}+1+\alpha^2+\alpha^3.
\end{aligned}
$$
Plugging these into
$$
\alpha^{-5}=\alpha^{-3}+\alpha^{-2}+1+\alpha
$$
gives
$$
\alpha^{-5}=\alpha^{-1}+1+\alpha^2+\alpha^4.
$$
At this point freshman’s dream gives
$$
\alpha^{-10}=\alpha^{-2}+1+\alpha^4+\alpha^8=\alpha+\alpha^3+\alpha^8=1+\alpha^3,
$$
where in the last step I reduced it with $(*)$ like a good boy.

To finish off this gives (with our earlier formula for $\alpha^{-1}$)
$$
\alpha^{-11}=\alpha^{-1}+\alpha^2=\alpha+\alpha^4+\alpha^5.
$$

As you see this is not a remedy that will make calculations like this trivial. In smaller fields you get more useful ‘coincidences’, and can work wonders.