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.
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 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 , so that 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 as above.
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 modulo , 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 of the so that the inequality holds. Now standard factorization methods can calculate the zeroes of over the integers.
- D. Coppersmith (1996). Finding a Small Root of a Univariate Modular Equation. Lecture Notes in Computer Science. 1070. pp. 155–165. doi:10.1007/3-540-68339-9_14. ISBN 978-3-540-61186-8.
- D. Coppersmith (1996). Finding a Small Root of a Bivariate Integer Equation; Factoring with high bits known. Lecture Notes in Computer Science. 1070. pp. 178–189. doi:10.1007/3-540-68339-9_16. ISBN 978-3-540-61186-8.
- Bauer, A.; Joux, A. (2007). Toward a Rigorous Variation of Coppersmith's Algorithm on Three Variables. Lecture Notes in Computer Science. 4515. pp. 361–378. doi:10.1007/978-3-540-72540-4_21. ISBN 978-3-540-72539-8.