# Coppersmith method

The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer zeroes of univariate or bivariate polynomials modulo a given integer. The method uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to find a polynomial that has the same zeroes as the target polynomial but smaller coefficients.

In cryptography, the Coppersmith method is mainly used in attacks on RSA when parts of the secret key are known and forms a base for Coppersmith's attack.

## Approach

Coppersmith’s approach is a reduction of solving modular polynomial equations to solving polynomials over the integers.

Let ${\displaystyle F(x)=x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}}$ and assume that ${\displaystyle F(x_{0})\equiv 0{\pmod {M}}}$ for some integer ${\displaystyle |x_{0}|. Coppersmith’s algorithm can be used to find this integer solution ${\displaystyle x_{0}}$.

Finding roots over Q is easy using e.g. Newton's method but these algorithms do not work modulo a composite number M. The idea behind Coppersmith’s method is to find a different polynomial ${\displaystyle F_{2}}$ related to F that has the same ${\displaystyle x_{0}}$ as a solution and has only small coefficients. If the coefficients and ${\displaystyle x_{0}}$ are so small that ${\displaystyle F_{2}(x_{0}) over the integers, then ${\displaystyle x_{0}}$ is a root of F over Q and can easily be found.

Coppersmith's algorithm uses LLL to construct the polynomial ${\displaystyle F_{2}}$ with small coefficients. Given F, the algorithm constructs polynomials ${\displaystyle p_{1}(x),p_{2}(x),\dots ,p_{n}(x)}$ that have the same zero ${\displaystyle x_{0}}$ modulo ${\displaystyle M^{a}}$, where a is some integer chosen dependent on the degree of F and the size of ${\displaystyle x_{0}}$. Any linear combination of these polynomials has zero ${\displaystyle x_{0}}$ modulo ${\displaystyle M^{a}}$.

The next step is to use the LLL algorithm to construct a linear combination ${\displaystyle F_{2}(x)=\sum c_{i}p_{i}(x)}$ of the ${\displaystyle p_{i}}$ so that the inequality ${\displaystyle |F_{2}(x)| holds. Now standard factorization methods can calculate the zeroes of ${\displaystyle F_{2}(x)}$ over the integers.