SMALL SOLUTIONS TO POLYNOMIAL EQUATIONS, AND LOW EXPONENT RSA VULNERABILITIES

We show how to find sufficiently small integer solutions to a polynomi al in a single variable module N, and to a polynomial in two variables over the integers. The methods sometimes extend to more variables. As applications: RSA encryption with exponent 3 is vulnerable if the opp onent knows two-thirds of the message, or if two messages agree over e ight-ninths of their length; and we can find the factors of N = P Q if we are given the high order 1/4 log(2) N bits of P.