Taylor and Francis Group, Journal of Discrete Mathematical Sciences and Cryptography, 2(12), p. 121-137, 2009
DOI: 10.1080/09720529.2009.10698223
Full text: Unavailable
Let N = pq be an RSA modulus where p, q are large primes of the same bitsize and (N) = (p 1)(q 1). We study the class of the public exponents e for which there exist integers X, Y , Z satisfying eX + (N)Y = NZ; with jXY j < p 2 6 N 1 2 and all prime factors of jY j are less than 1040. We show that these exponents are of improper use in RSA cryptosystems and that their number is at least O N 1 2 " where " is a small positive constant. Our method combines continued fractions, Coppersmith's lattice-based technique for nding small roots of bivariate polynomials and H. W. Lenstra's elliptic curve method (ECM) for factoring.