The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer zeroes of univariate or bivariate polynomials, or their small zeroes 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.
Coppersmith's approach is a reduction of solving modular polynomial equations to solving polynomials over the integers.
and assume that
( mod
Coppersmith’s algorithm can be used to find this integer solution
Finding roots over Q is easy using, e.g., Newton's method, but such an algorithm does not work modulo a composite number M. The idea behind Coppersmith’s method is to find a different polynomial f related to F that has the same root
modulo M, but has only small coefficients.
If the coefficients and
are small enough that
over the integers, then we have
is a root of f over Q and can be found easily.
More generally, we can find a polynomial
with the same root
modulo some power
of M, satisfying
, and solve for
Coppersmith's algorithm uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to construct the polynomial f with small coefficients.
Given F, the algorithm constructs polynomials
that all have the same root
, where a is some integer chosen based on the degree of F 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
so that the inequality
holds.
Now standard factorization methods can calculate the zeroes of
over the integers.
Coppersmith's method for univariate polynomials is implemented in