# Coppersmith method

The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer roots of polynomial equations. These polynomials can be univariate or bivariate. In cryptography the algorithm is mainly used in attacks on RSA when parts of the secret key are known.

The method uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to find a polynomial that has the roots of the target polynomial as roots and has small coefficients.

## Approach

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 $F_{2}$ related to F that has the same $x_{0}$ as a solution and has only small coefficients. If the coefficients and $x_{0}$ are so small that $F_{2}(x_{0}) over the integers, then $x_{0}$ is a root of F over Q and can easily be found.

## Computing small roots

Coppersmith’s approach is a reduction of solving modular polynomial equations to solving polynomials over the integers. Coppersmith's algorithm uses LLL to construct the polynomial $F_{2}$ with small coefficients.

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