A note on the bivariate Coppersmith theorem (Q2377067): Difference between revisions

In this note the authors provide a proof of a result of \textit{D. Coppersmith} [J. Cryptology 10, No. 4, 233--260 (1997; Zbl 0912.11056)], whose original proof they claim to be incomplete. That result, Corollary 2 of the Coppersmith's paper and quoted here as Corollary 1, assures that we can efficiently compute all the roots \((x_0,y_0)\), with \(x_0,y_0\) bounded, of an irreducible bivariate polynomial \(p(x,y)\) defined over the integers. Such a result is related with an attack to a particular instance of the RSA cryptosystem. The note also points out that the gap in the paper of Coppersmith also exists in other papers inspired by it, in particular in two papers of the first author of the present note, and that the solution proposed here ``applies to those other papers as well''. The engaged proof of Corollary 1 is given in the Section 2 of the Note (Lemmas 1 and 2).