# Cubic root of a polynomial to modulo of another polynomial

Is there any algorithm to solve problems like the problem below, any ideas?

Find polynomial $f$ such that:

$f^3 \equiv x^4 + x^2 \ (mod\ x^{10} + x^3 + 1)$

All numeric coefficients are from $\mathbf{Z_2}$.

• This looks to me like a discrete logarithm problem. You’re working in $k=\Bbb F_{1024}$, whose multiplicative group is of order $1023=3\cdot11\cdot31$. Since $(x^4+x^2)^{341}=1$ in this field, your element is indeed a cube. The group $k^\times$ is cyclic, happens to be generated by $x$, and if you know the value of $n$ such that $x^n=x^4+x^2$, the answer is clear. Beyond this point, this nonspecialist in the field can not help you. May 19, 2017 at 23:13

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.

• Well, I certainly never would have been able to do this. May 23, 2017 at 3:50
• This is analogous to index calculus for solving the DLP in $\Bbb{Z}_p^*$. There one keeps multiplying with the given primitive root $g$, and looks for those powers of $g$ that only have relatively small prime factors after reduction modulo $p$ (i.e. smooth remainders for a prescribed level of smoothness). Here it is natural to use low degree polynomials as substitutes of small primes. May 24, 2017 at 14:48
• Well, my admiration of your calculation is undiminished. May 24, 2017 at 14:56