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.
Coppersmith's method for univariate polynomials is implemented in
- Magma as the function
- PARI/GP as the function
- SageMath as the method
- Coppersmith, D. (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. ISBN 978-3-540-61186-8.
- Coppersmith, D. (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. ISBN 978-3-540-61186-8.
- Coron, J. S. (2004). "Finding small roots of bivariate integer polynomial equations revisited" (PDF). Lecture Notes in Computer Science. 3027: 492–505. doi:10.1007/978-3-540-24676-3_29.
- 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. ISBN 978-3-540-72539-8.
- Coron, J. S. (2007). "Finding small roots of bivariate integer polynomial equations: A direct approach" (PDF). Lecture Notes in Computer Science. 4622: 379–394. doi:10.1007/978-3-540-74143-5_21.