4
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Lubin
    May 19, 2017 at 23:13

1 Answer 1

5
+150
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Well, I certainly never would have been able to do this. $\endgroup$
    – Lubin
    May 23, 2017 at 3:50
  • $\begingroup$ 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. $\endgroup$ May 24, 2017 at 14:48
  • 2
    $\begingroup$ Well, my admiration of your calculation is undiminished. $\endgroup$
    – Lubin
    May 24, 2017 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .