International Association
for Cryptologic Research

Abstract  In 1997, Coppersmith proved a famous theorem for finding small roots of bivariate polynomials over ℤ, with important applications

to cryptography.

While it seems to have been overlooked until now, we found the proof of the most commonly cited version of this theorem to

be incomplete. Filling in the gap requires technical manipulations which we carry out in this paper.

• Content Type Journal Article
• Pages 1-5
• DOI 10.1007/s00145-012-9121-x
• Authors

  • Jean-Sébastien Coron, Université du Luxembourg, 6, rue Richard Coudenhove-Kalergi, 1359 Luxembourg, Luxembourg
  • Alexey Kirichenko, F-Secure Corporation, Tammasaarenkatu 7, PL 24, 00181 Helsinki, Finland
  • Mehdi Tibouchi, NTT Information Sharing Platform Laboratories, 3-9-1 Midori-cho, Musashino-shi, Tokyo, 180-8585 Japan

• Journal Journal of Cryptology
• Online ISSN 1432-1378
• Print ISSN 0933-2790

From: Tue, 20 Mar 2012 16:51:58 GMT