This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)(Learn how and when to remove this template message)
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 these algorithms do not work modulo a composite number M. The idea behind Coppersmith’s method is to find a different polynomial related to F that has the same as a solution and has only small coefficients. If the coefficients and are so small that over the integers, then is a root of F over Q and can easily be found.
Coppersmith's algorithm uses LLL to construct the polynomial with small coefficients. Given F, the algorithm constructs polynomials that have the same zero modulo , where a is some integer chosen dependent on the degree of F and the size of . Any linear combination of these polynomials has zero 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: 155–165. doi:10.1007/3-540-68339-9_14.
- D. Coppersmith (1996). "Finding a Small Root of a Bivariate Integer Equation; Factoring with high bits known". Lecture Notes in Computer Science. 1070: 178–189. doi:10.1007/3-540-68339-9_16.
- Bauer, A.; Joux, A. (2007). "Toward a Rigorous Variation of Coppersmith's Algorithm on Three Variables". Lecture Notes in Computer Science. 4515: 361–378. doi:10.1007/978-3-540-72540-4_21.