Let  be an RSA modulus with  In this paper, we analyze the security of RSA with the class of the exponents e satisfying an equation  with

     and

where  is the greatest integer less than or equal to x. Using the continued fraction algorithm and Coppersmith’s lattice reduction method for solving polynomial equations, we show that such exponents lead to the factorization of N in polynomial time. Additionally, we show that the class of such weak exponents is large, namely that their number is at least  where  is a small constant depending only on N.

RSA, cryptanalysis, factorization, continued fraction, Coppersmith’s method.