ABSTRACT
At a cryptography conference in 1996, Coppersmith [30] (see also [31]) showed how lattice basis reduction could be used to find small roots of modular polynomial equations in one variable. Coppersmith’s algorithm implies that RSA cryptosystems with low public exponents can be broken in polynomial time using the LLL algorithm. In this chapter, we present the basic ideas underlying this algorithm, following Coppersmith [32, 33] and Howgrave-Graham [66]. The great impact of these ideas on cryptography is discussed in the survey papers by Coupe´ et al. [34], Nguyen and Stern [108, 109], and May [94].
