Abstract
At Eurocrypt ‘96, Coppersmith proposed an algorithm for finding small roots of bivariate integer polynomial equations, based on lattice reduction techniques. But the approach is difficult to understand. In this paper, we present a much simpler algorithm for solving the same problem. Our simplification is analogous to the simplification brought by Howgrave-Graham to Coppersmith’s algorithm for finding small roots of univariate modular polynomial equations. As an application, we illustrate the new algorithm with the problem of finding the factors of n=pq if we are given the high order 1/4 log2 n bits of p.
Chapter PDF
Similar content being viewed by others
References
Boneh, D., Durfee, G.: Crypanalysis of RSA with private key d less than N0.292. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 1. Springer, Heidelberg (1999)
Boneh, D., Durfee, G., Howgrave-Graham, N.A.: Factoring n = p r q for large r. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 326. Springer, Heidelberg (1999)
Coppersmith, D.: Finding a Small Root of a Univariate Modular Equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155–165. Springer, Heidelberg (1996)
Coppersmith, D.: Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 178–189. Springer, Heidelberg (1996)
Coppersmith, D.: Small solutions to polynomial equations, and low exponent vulnerabilities. J. of Cryptology 10(4), 233–260 (1997); Revised version of two articles of Maurer, U.M. (ed.): EUROCRYPT 1996. LNCS, vol. 1070, pp. 233–260. Springer, Heidelberg (1996)
Coppersmith, D.: Finding small solutions to small degree polynomials. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, p. 20. Springer, Heidelberg (2001)
Howgrave-Graham, N.A.: Finding small roots of univariate modular equations revisited. In: Darnell, M.J. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 131–142. Springer, Heidelberg (1997)
Jutla, C.S.: On finding small solutions of modular multivariate polynomial equations. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 158–170. Springer, Heidelberg (1998)
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Ann. 261, 513–534 (1982)
Maurer, U.: Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters. Journal of Cryptology 8(3), 123–155 (1995)
Mignotte, M.: An inequality about factors of polynomials. Math. Comp. 28, 1153–1157 (1974)
Nguyen, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, p. 146. Springer, Heidelberg (2001)
Shoup, V.: OAEP reconsidered. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 239. Springer, Heidelberg (2001)
Shoup, V.: Number Theory C++ Library (NTL) version 5.3.1, Available at http://www.shoup.net
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Coron, JS. (2004). Finding Small Roots of Bivariate Integer Polynomial Equations Revisited. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_29
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive