Application of ECM to a class of RSA keys
Abderrahmane Nitaj · Journal of Discrete Mathematical Sciences and Cryptography · 2009
Let N = pq be an RSA modulus where p, q are large primes of the same bitsize and ϕ(N) = (p − l)(q − 1). We study the class of the public exponents e for which there exist integers X, Y, Z satisfying with and all prime factors of |Y| are less than 1040. We show that these exponents are of improper use in RSA cryptosystems and that their number is at least where ε is a small positive constant. Our method combines continued fractions, Coppersmith’s lattice-based technique for finding small roots of bivariate polynomials and H. W. Lenstra’s elliptic curve method (ECM) for factoring.