Intereting Posts

Why this two spaces do not homeomorphic?
Effect of the degree of a map $S^n\to M$ on lower homology groups
Expected value: Random sequence
How are primitive mathematical objects chosen?
The equivalence of an integral and a sum of integrals
Show that $X \times Y \rightarrow Y$ is a closed map. Give an example where projection to the first factor is not a closed map.
Use induction to prove that $F_n \ge \sqrt 2 ^n$ for $n \ge 6$
Does the change of variable function have to be injective?
The use of conjugacy class and centralizer?
Finite-dimensional space naturally isomorphic to its double dual?
Unique intermediate subgroup and double coset relation I
Struggling with “technique-based” mathematics, can people relate to this? And what, if anything, can be done about it?
Primary/Elementary Pedagogy: What is the rationale for the absent '+' in mixed fractions?
How to perform a fair coin toss experiment over phone?
Metric spaces problem

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)$ ?

- An odd question about induction.
- Binary long division for polynomials in CRC computation
- Using 8x8 Binary Matrices as a hash
- Floor function to the base 2
- Is there a sequence of primes whose decimal representations are initial segments of each other?
- How do you work with the IEEE 754 32-bit floating point format?

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

- A proof that powers of two cannot be expressed as the sum of multiple consecutive positive integers that uses binary representations?
- Determining the position of a binary value with $k$ one bits and $n-k$ zeros in an enumeration of $C_k^n$ bit strings
- Proof/intuition that any number can be expressed in binary form and every number will have a unique representation?
- Find the neighbors in Gray Code sequence
- Binary long division for polynomials in CRC computation
- Understanding Reed-Solomon as it applies to Shamir secret sharing
- Construct generator matrix given generator polynomial?
- Can all linear code be adapted so that the first bits of the encoded message are the bits from the original message?
- The sum of a polynomial over a boolean affine subcube
- A serious problem in Bijection in a Algo

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.

- Good Physical Demonstrations of Abstract Mathematics
- Examples of Baire class 2 functions
- A Wi-Fi password hidden in statistics expression
- Can $\ln(x)=\lim_{n\to\infty} n\left(x^{\frac1{n}}-1 \right)$ be expressed as an infinite telescoping product?
- Coupon collector's problem using inclusion-exclusion
- Prove that any rational can be expressed in the form $\sum\limits_{k=1}^n{\frac{1}{a_k}}$, $a_k\in\mathbb N^*$
- A Pick Lemma like problem
- How to find the period of the sum of two trigonometric functions
- Playing Odd-Even Cricket, is there a perfect strategy
- Relationship Between Ratio Test and Power Series Radius of Convergence
- Inverse of Heine–Cantor theorem
- Can we have a matrix whose elements are other matrices as well as other things similar to sets?
- Homology of a vector space modulo a finite group
- Are isomorphic the following two links?
- Solving an equality in 2 variables