Finding element in binary representation of $GF(2^6)$

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.