Coppersmith method

Coppersmith's approach is a reduction of solving modular polynomial equations to solving polynomials over the integers.

Let ${\displaystyle F(x)=x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}}$ and assume that ${\displaystyle F(x_{0})\equiv 0{\pmod {M}}}$ for some integer ${\displaystyle |x_{0}|<M^{1/n}}$. Coppersmith’s algorithm can be used to find this integer solution ${\displaystyle x_{0}}$.

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 ${\displaystyle x_{0}}$ modulo M, but has only small coefficients. If the coefficients and ${\displaystyle x_{0}}$ are small enough that ${\displaystyle |f(x_{0})|<M}$ over the integers, then we have ${\displaystyle f(x_{0})=0}$, so that ${\displaystyle x_{0}}$ is a root of f over Q and can be found easily. More generally, we can find a polynomial ${\displaystyle f(x)}$ with the same root ${\displaystyle x_{0}}$ modulo some power ${\displaystyle M^{a}}$ of M, satisfying ${\displaystyle |f(x_{0})|<M^{a}}$, and solve for ${\displaystyle x_{0}}$ 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 ${\displaystyle p_{1}(x),p_{2}(x),\dots ,p_{n}(x)}$ that all have the same root ${\displaystyle x_{0}}$ modulo ${\displaystyle M^{a}}$, where a is some integer chosen based on the degree of F and the size of ${\displaystyle x_{0}}$. Any linear combination of these polynomials also has ${\displaystyle x_{0}}$ as a root modulo ${\displaystyle M^{a}}$.

The next step is to use the LLL algorithm to construct a linear combination ${\displaystyle f(x)=\sum c_{i}p_{i}(x)}$ of the ${\displaystyle p_{i}(x)}$ so that the inequality ${\displaystyle |f(x_{0})|<M^{a}}$ holds. Now standard factorization methods can calculate the zeroes of ${\displaystyle f(x)}$ over the integers.

Coppersmith's method for univariate polynomials is implemented in

• Magma as the function SmallRoots;
• PARI/GP as the function zncoppersmith;
• SageMath as the method small_roots.

• Coppersmith, D. (1996). "Finding a Small Root of a Univariate Modular Equation". Advances in Cryptology — EUROCRYPT '96. Lecture Notes in Computer Science. Vol. 1070. pp. 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". Advances in Cryptology — EUROCRYPT '96. Lecture Notes in Computer Science. Vol. 1070. pp. 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). Advances in Cryptology - EUROCRYPT 2004. Lecture Notes in Computer Science. Vol. 3027. pp. 492–505. doi:10.1007/978-3-540-24676-3_29. ISBN 978-3-540-21935-4.
• Bauer, A.; Joux, A. (2007). "Toward a Rigorous Variation of Coppersmith's Algorithm on Three Variables". Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. Vol. 4515. pp. 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). Advances in Cryptology - CRYPTO 2007. Lecture Notes in Computer Science. Vol. 4622. pp. 379–394. doi:10.1007/978-3-540-74143-5_21. ISBN 978-3-540-74142-8.