Jtdylktuy

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}$.

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}toBbb{Z}/1023Bbb{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^3equiv 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^7equiv 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 $$2log p_1+2log p_3equiv 3.$$
  


• Equation 8) tells us that $$log p_2+log p_3equiv 31.$$
  


• Equation 17) tells us that $$6log p_1+log p_2equiv 57.$$
  

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

Returning to your problem. We now know that
$$
log(x^4+x^2)=log(x^2(x+1)^2)=2+2log(x+1)=156.
$$
Let's write $y=log f$, so $log(f^3)=3y$.
Because $3mid 1023$, the congruence $3yequiv156pmod{1023}$ has 3 solutions: $yequiv 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=3cdot11cdot31$. 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.