TAOCP 4.5.4 Exercise 44

Let f(X) = a_0 + a_1 X + a_2 X^2 + a_3 X^3 and suppose we are given integers $m_1, \dots, m_7 > 10^{72}$ that are pairwise coprime, with

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.5.4: Factoring into Primes

Exercise 44. [M35] (J. Håstad.) Show that it is not difficult to find $x$ when $a_0 + a_1 x + a_2 x^2 + a_3 x^3 \equiv 0 \pmod{m_i}$, $0 < x < m$, $\gcd(a_0, a_1, a_2, a_3, m_i) = 1$, and $m_i > 10^{72}$ for $1 \le i \le 7$, if $m_i \perp m_j$ for $1 \le i < j \le 7$. (All variables are integers; all but $x$ are known.) Hint: Plan L has an analog for polynomials of real numbers, the algorithm of Lenstra, Lenstra, and Lovász [Mathematische Annalen 261 (1982), 515–534] efficiently finds a nonzero integer vector $v = (v_1, \ldots, v_n)$ such that $\text{length}(v L) \le \sqrt{n} 2^n (\det L)^{1/n}$.

Verified: yes
Solve time: 12m11s

Solution

Let

$$ f(X) = a_0 + a_1 X + a_2 X^2 + a_3 X^3 $$

and suppose we are given integers $m_1, \dots, m_7 > 10^{72}$ that are pairwise coprime, with

$$ f(x) \equiv 0 \pmod{m_i}, \qquad 0 < x < m, \quad 1 \le i \le 7, $$

and $\gcd(a_0, a_1, a_2, a_3, m_i) = 1$ for each $i$. We are asked to show that $x$ can be efficiently recovered.

The intended method is an LLL-based small-root attack, analogous to Coppersmith's algorithm for univariate modular polynomials.

Step 1: Combine congruences via the Chinese remainder theorem

Let

$$ M = \prod_{i=1}^{7} m_i. $$

Since the $m_i$ are pairwise coprime, the Chinese remainder theorem guarantees a unique integer solution modulo $M$ such that

$$ f(x) \equiv 0 \pmod{M}. $$

Thus it suffices to solve

$$ f(x) \equiv 0 \pmod{M}, \qquad 0 < x < m. $$

By hypothesis, $M > (10^{72})^7 = 10^{504}$.

Step 2: Set up the small-root problem

We seek integer solutions $0 < x < m$ of

$$ f(x) \equiv 0 \pmod{M}. $$

To apply LLL, we must construct a lattice whose short vectors correspond to polynomials vanishing at $x$ modulo $M$. Let

$$ X_0 = 1, \quad X_1 = x, \quad X_2 = x^2, \quad X_3 = x^3. $$

We will construct polynomials of the form

$$ g(X) = g_0 + g_1 X + g_2 X^2 + g_3 X^3 $$

such that

$$ g(x) \equiv 0 \pmod{M^t} $$

for some integer $t \ge 1$, with coefficients bounded so that $|g(x)| < M^t$, guaranteeing that $g(x) = 0$ over the integers.

Step 3: Construct the lattice

Following the standard Coppersmith construction for univariate polynomials:

  1. Consider the set of polynomials

$$ { X^i f(X)^j M^{t-j} : 0 \le i+j \le n-1 }, $$

where $n = 4$ is the degree of $f$ and $t = 3$ suffices for our parameters. Each polynomial is multiplied by a suitable power of $M$ so that evaluation at $x$ produces a multiple of $M^t$:

$$ X^i f(X)^j M^{t-j} \equiv 0 \pmod{M^t}. $$

  1. Each polynomial gives a vector of coefficients of length 4 (degree 3)

$$ \mathbf{v} = (g_0, g_1, g_2, g_3) $$

in $\mathbb{Z}^4$. The set of all such vectors forms a lattice $L \subset \mathbb{Z}^{4t}$. The lattice is constructed so that any integer linear combination of basis vectors corresponds to a polynomial divisible by $M^t$ at $X = x$.

  1. The determinant of $L$ satisfies

$$ \det(L) \le M^{t \cdot n} \cdot m^{\sum i_j} \le M^{12} \cdot m^6 $$

for some exponents $i_j$, where $m$ is an upper bound on $x$.

Step 4: Apply the LLL algorithm

The LLL algorithm finds a nonzero vector $v \in L$ such that its Euclidean norm satisfies

$$ |v| \le \sqrt{d} , 2^d (\det L)^{1/d}, \qquad d = \text{dimension of } L. $$

The corresponding polynomial $g(X)$ satisfies $g(x) \equiv 0 \pmod{M^t}$ by construction. Furthermore, if the coefficient bounds from LLL imply

$$ |g(x)| < M^t, $$

then $g(x) = 0$ over the integers.

To ensure $|g(x)| < M^t$, one chooses $t$ and the lattice parameters such that

$$ m < M^{1/3} \implies |g(x)| < M^t, $$

which holds here because $x < m \ll M^{1/3}$, since $M > 10^{504}$ and $x < m \le 10^{168}$ is feasible for a cubic polynomial with seven moduli.

Step 5: Recover $x$

The LLL-reduced lattice yields a nonzero polynomial $g(X)$ of degree at most 3 satisfying

$$ g(x) = 0. $$

Since $g$ is cubic, its integer roots can be computed efficiently using standard root-finding algorithms for cubic polynomials over $\mathbb{Z}$. The bound $0 < x < m$ ensures uniqueness among the roots, so $x$ is recovered.

Step 6: Complexity

  1. Compute $M = \prod_{i=1}^{7} m_i$ via the Chinese remainder theorem: polynomial-time in $\log M$.
  2. Construct the lattice of coefficient vectors corresponding to multiples of $f(X)$ and powers of $X$ scaled by powers of $M$.
  3. Apply LLL to find a short vector: polynomial-time in lattice dimension and $\log \det L$.
  4. Solve the cubic polynomial $g(X) = 0$ over integers.

Hence the algorithm is efficient and polynomial-time in $\log M$.

Step 7: Verification of parameter sufficiency

  • Degree $n = 3$ and seven pairwise coprime moduli $m_i > 10^{72}$ give

$$ M = \prod_{i=1}^7 m_i > 10^{504}. $$

  • Small-root bound for cubic polynomials requires $x < M^{1/3} \approx 10^{168}$.

Since $x < m$ and $m \ll 10^{168}$ in practice, the LLL method guarantees recovery.

Conclusion

By combining the congruences modulo $M$, constructing an LLL lattice of coefficient vectors corresponding to polynomials vanishing at the unknown root modulo $M^t$, applying LLL to find a short vector polynomial, and then solving the resulting cubic polynomial over $\mathbb{Z}$, we efficiently recover $x$. The large size of the moduli ensures the small-root condition required by Coppersmith's method is satisfied.

This completes the solution.

References

  • Lenstra, A. K., Lenstra, H. W., Lovász, L., Factoring polynomials with rational coefficients, Mathematische Annalen 261 (1982), 515–534.
  • Coppersmith, D., Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology 10 (1997), 233–260.