Intereting Posts

unorthodox solution of a special case of the master theorem
${\gcd(n,m)\over n}{n\choose m}$ is an integer
Show that $x(x+1) = y^4+y^3+ay^2+by+c$ has a finite number of positive integral solutions.
When an infinite union of countable sets is uncountable?
How to prove $\left(1+\frac{1}{\sin a}\right)\left(1+\frac{1}{\cos a}\right)\ge 3+2\sqrt{2}$?
Calculate $\int \limits {x^n \over 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+…+\frac{x^n}{n!}} dx$ where $n$ is a positive integer.
Extension and contraction of ideals in polynomial rings
Complex Exponents
How many solutions does this equation have $x^2 \equiv 1017 (\mod 2^k)$
Infinite Prime Numbers: With Fermat Numbers
How to reparametrize curves in terms of arc length when arc-length evaluation cannot be computed analytically
How many ways are there to express a number as the product of groups of three of its factors?
Elementary proof for $\sqrt{p_{n+1}} \notin \mathbb{Q}(\sqrt{p_1}, \sqrt{p_2}, \ldots, \sqrt{p_n})$ where $p_i$ are different prime numbers.
Chess Master Problem
Infinite Inclusion and Exclusion in Probability

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

- How to calculate no. of binary strings containg substring “00”?
- Using 8x8 Binary Matrices as a hash
- What is the relation between this binary number with no two 1 side by side and fibonacci sequence?
- Algorithm for creating binary rational numbers
- Rounding - should I compare truncated sum with the number added to make least bigger number
- The sum of powers of two and two's complement – is there a deeper meaning behind this?

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

- Maximal Hamming distance
- why binary is read right to left
- How to calculate no. of binary strings containg substring “00”?
- Algorithm for creating binary rational numbers
- How original RS codes and the corresponding BCH codes are related?
- Generating a binary code with maximized Hamming distance
- Is there a $(6,9,3)_2$ code?
- Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?
- Cryptography and Coding Theory
- Set of points of $[0,1)$ that have a unique binary expansion

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.

- Solving $x^k+(x+1)^k+(x+2)^k+\cdots+(x+k-1)^k=(x+k)^k$ for $k\in\mathbb N$
- Representation theory of locally compact groups
- Prove the following integral inequality: $\int_{0}^{1}f(g(x))dx\le\int_{0}^{1}f(x)dx+\int_{0}^{1}g(x)dx$
- Order of general linear group of $2 \times 2$ matrices over $\mathbb{Z}_3$
- Can you give an example of a complex math problem that is easy to solve?
- Calculating line integrals via Stokes theorem
- Properties of the “A transpose A” (A-transpose-A, ${\bf A}^{\rm T}{\bf A}$ or ${\bf A^{\rm '}A}$) matrix
- please solve a 2013 th derivative question?
- Is there an algorithm for writing an integer as a difference of squares?
- Compute the inverse Laplace transform of $e^{-\sqrt{z}}$
- Jacobian matrix and Hessian matrix identity
- Is $1+2+3+4+\cdots=-\frac{1}{12}$ the unique ''value'' of this series?
- Difference between limit superior & supremum of a sequence
- Find $ \int \frac {\tan 2x} {\sqrt {\cos^6x +\sin^6x}} dx $
- Matrices that are not diagonal or triangular, whose eigenvalues are the diagonal elements