How to find the n-th root of a polynomial in a binary field?

The question states the following:

Let us consider the field $𝐺𝐹(2^4)$ with multiplication modulo $𝑥^4+𝑥^3+1$, find all $y$ such that $y^{33} = 0101$.

My first approach was finding another way to write the polynomial in the field which can be accomplished by writing it like so: $0101$ = $x^2+1 = (x+1)(x+1)$ then I tried to write argue that since $y^{32} * y = y^{33}$ then y should be $y=x+1$.

I don't know if this is the correct solution or the correct approach, I am expected to do a similar exercise in the exam without calculator or a computer so any guidance on how to approach this problem in order to get $\sqrt[33](x^2+1)$ would be greatly appreciated.

For this problem, it is perhaps equally easy to just try every element of $\Bbb F_{2^4}^\times$. But I'm trying to present a method that potentially works for much larger inputs.

Let $q = p^r$ be a prime power such that $q \equiv 7\pmod 9$, e.g. $q = 2^4$. There is a trick that can easily check whether an element $x \in \Bbb F_q^\times$ is a cubic, and in case it is, we get one cubic root of $x$.

Assume that there exists $z$ such that $z^3 = x$. Then we will have $x^{(q - 1)/3} = z^{q - 1} = 1$. This means that, if we take $y = x^{(q + 2)/9}$, then we get $y^3 = x^{(q + 2)/3} = x$.

Thus you just compute $y = x^{(q + 2)/9}$ and check whether $y^3 = x$ holds. If it doesn't hold, then $x$ has no cubic root in $\Bbb F_q$; otherwise $y$ is a cubic root and the other two cubic roots are obtained by multiplying $y$ with the two primitive cubic roots of unity.

The remaining task is how to obtain the two primitive cubic roots of unity. One method is to pick a random element $t \in \Bbb F_q^\times$ and calculate $s = t^{(q - 1)/3}$. There is a $\frac 1 3$ chance that you end up with $s = 1$, in which case you simply repick another random element, until you get $s \neq 1$. At that point you know that $s$ is a primitive cubic root of unity, and the other one is $-1 - s$.

WhatsUp gave you the theory (+1), so I proceed with a trick answer. The problem with my trick answers is that they are a bit ad hoc, and don't always work. Not unlike those mental arithmetic tricks where you need to spot a familiar pattern that you can take advantage of. But I have spent a bit of time with finite fields, and I want to share.

The remaining task is to find whether $0101=(0011)^2$ has a cube root or not in this field. And if it does, to find them. I prefer to write $\alpha=x+\langle x^4+x^3+1\rangle$ for the coset of $x$ modulo $x^4+x^3+1$. So my $\alpha$ is your $0010$, and we are looking for cube roots of $(\alpha+1)^2$.

It would be easy, if we could find a cube root of $\alpha+1$, right? Ok. Let's recall that $\alpha^4+\alpha^3+1=0$. I will rewrite that first in the form $$ \alpha^4+\alpha^3=1.\qquad(*) $$ Then I divide $(*)$ by $\alpha^3$ and arrive at $$ \alpha+1=\frac1{\alpha^3}=(1/\alpha)^3. $$ There! We now know that $1/\alpha$ is (one of) the cube root(s) of $\alpha+1$. As WhatsUp explained, not all elements of $GF(16)$ have cube roots, but we were lucky to spot that $\alpha+1$ does.

You probably want to write $1/\alpha$ in one of the more common forms. To that end simply divide $(*)$ by $\alpha$ instead to see that $$ \alpha^2+\alpha=\frac1{\alpha}. $$ So $1/\alpha=\alpha^2+\alpha=0110$, and one of the cube roots of $0101$ is thus $$(1/\alpha)^2=(0110)^2=\alpha^4+\alpha^2=\alpha^3+1+\alpha^2=1101. $$

By WhatsUp's answer the equation has three solutions altogether. You get the others by multiplying $1101$ with a non-trivial third root of unity. And you can generate those by raising random elements to the fifth power ($(16-1)/3=5$). Hop to it!