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 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 and assume that for some
integer.
Coppersmith’s algorithm can be used to find this integer solution.
Finding roots over is easy using, e.g., Newton's method, but such an algorithm does not work modulo a composite number. The idea behind Coppersmith’s method is to find a different polynomial related to that has the same root modulo, but has only small coefficients. If the coefficients and are small enough that over the integers, then we have, so that is a root of over and can be found easily. More generally, we can find a polynomial with the same root modulo some power of, satisfying, and solve for as above.
Coppersmith's algorithm uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm to construct the polynomial with small coefficients.
Given, the algorithm constructs polynomials that all have the same root modulo, where is some integer chosen based on the degree of and the size of.
Any linear combination of these polynomials also has as a root modulo.
The next step is to use the LLL algorithm to construct a linear combination
of the so that the inequality holds.
Now standard factorization methods can calculate the zeroes of over the integers.