Cubic root of a polynomial to modulo of another polynomial

As Lubin pointed out this can be viewed as a discrete logarithm problem. I assume that the polynomial $p(x):=x^{10}+x^3+1$ is known to be primitive, so the coset of $x$ is generator of the multiplicative group of $\Bbb{F}_{2^{10}}=\Bbb{F_2}[x]/\langle p(x)\rangle$. Therefore the discrete logarithm in base $x$ is a well-defined function $\log:\Bbb{F}_{1024}\to\Bbb{Z}/1023\Bbb{Z}$. Finding $f$ is more or less equivalent to finding $\log f$ (because exponentiation is fast by virtue of square-and-multiply).

We are given that $f^3\equiv x^2(x+1)^2$. Obviously $\log x=1$, so to calculate the discrete log of the r.h.s. we need to figure out $\log(x+1)$. Let's try a method known as index calculus. One idea is to collect polynomials with known discrete logarithms. While doing that I also keep factoring those polynomials I can. The second idea is to generate enough many equations involving logarithms of a chosen set of low degree polynomials so that eventually those equations allow us to solve for the logarithms of interest. I don't know of a good set of such low degree polynomials in advance, so I play it by the ear.

Modulo the polynomial $p(x)$ we have the following congruences. The first three are just rewriting the equation $x^{10}+x^3+1=0$ in various ways. Then I keep multiplying an earlier congruence with the lowest power of $x$ so that I get something new by reducing it modulo $p(x)$. Then I factor the remainder, iff I can do it with factors of degrees $\le4$ (I have memorized those, so it goes fast). Here's what I get: $$ \begin{aligned} 1)&& x^{10}&\equiv x^3+1=(x+1)(x^2+x+1)\\ 2)&& x^{-3}&\equiv x^7+1=(x+1)(x^3+x+1)(x^3+x^2+1)\\ 3)&& x^3&\equiv x^{10}+1=(x+1)^2(x^4+x^3+x^2+x+1)^2\\ 4)&& x^{17}&\equiv x^{10}+x^7\equiv x^7+x^3+1\\ 5)&& x^{20}&\equiv x^6+1=(x+1)^2(x^2+x+1)^2&\text{1st squared}\\ 6)&& x^{24}&\equiv x^{10}+x^4=x^4+x^3+1\\ 7)&& x^{30}&\equiv x^{10}+x^9+x^6=x^9+x^6+x^3+1=(x+1)^3(x^2+x+1)^3&\text{1st cubed}\\ 8)&& x^{31}&\equiv x^7+x^4+x^3+x+1=(x^3+x^2+1)(x^4+x^3+x^2+x+1)\\ 9)&& x^{34}&\equiv x^7+x^6+x^4+1=(x+1)(x^2+x+1)(x^4+x^3+1)&\text{6th and 1st}\\ 10)&& x^{37}&\equiv x^9+x^7+1\\ 11)&& x^{38}&\equiv x^8+x^3+x+1\\ 12)&& x^{40}&\equiv x^5+x^2+1\\ 13)&& x^{45}&\equiv x^7+x^5+x^3+1\\ 14)&& x^{48}&\equiv x^8+x^6+1&\text{6th squared}\\ 15)&& x^{50}&\equiv x^8+x^3+x^2+1=(x+1)(x^2+x+1)(x^5+x^2+1)&\text{1st and 12th}\\ 16)&& x^{52}&\equiv x^5+x^4+x^3+x^2+1\\ 17)&& x^{57}&\equiv x^9+x^8+x^7+x^5+x^3+1=(x+1)^6(x^3+x^2+1) \end{aligned} $$ At this point we notice that we know quite a bit about the logarithms of the polynomials $p_1(x)=x+1$, $p_2(x)=x^3+x^2+1$ and $p_3(x)=x^4+x^3+x^2+x+1$. The discrete logs are determined modulo $2^{10}-1=1023$ so below all the congruences are modulo $1023$.

• Equation 3) tells us that $$2\log p_1+2\log p_3\equiv 3.$$
• Equation 8) tells us that $$\log p_2+\log p_3\equiv 31.$$
• Equation 17) tells us that $$6\log p_1+\log p_2\equiv 57.$$

Eliminating $\log p_2$ from the latter two congruences gives $$ 6\log p_1-\log p_3\equiv 26. $$ Eliminating $\log p_3$ from this and the first congruence gives $$ 14\log p_1\equiv 55. $$ This congruence has a unique solution $$ \log p_1\equiv 77. $$

Returning to your problem. We now know that $$ \log(x^4+x^2)=\log(x^2(x+1)^2)=2+2\log(x+1)=156. $$ Let's write $y=\log f$, so $\log(f^3)=3y$. Because $3\mid 1023$, the congruence $3y\equiv156\pmod{1023}$ has 3 solutions: $y\equiv 52,393,734$. Therefore the solutions for $f$ are $$ \begin{aligned} x^{52}&\equiv x^5+x^4+x^3+x^2+1 &\text{we accidentally did this above!}\\ x^{393}&\equiv x^9+x^8+x^6+x^5+x^3+x^2\\ x^{734}&\equiv x^9+x^8+x^6+x^4+1. \end{aligned} $$ As a final check we see that the three solutions sum up to zero. This is to be expected because they are gotten from each other by multiplication by a third root of unity $\omega=x^{341}$ and $1+\omega+\omega^2=0$.

A final note. It may easily turn out that this time we could have solved the discrete logarithm of $x+1$ faster by using the Chinese Remainder Theorem and the fact that $1023=3\cdot11\cdot31$. We would have only needed the logarithm modulo $3$, $11$ and $31$ and then CRT-combine those. I just felt like doing a run of index calculus (possibly for future reference on site). Yet another alternative is the so called Baby step - Giant step -method.