On the Number of Sparse RSA Exponents

Abstract

An RSA modulus is a product M = pl of two primes p and l. We show that for almost all RSA moduli M, the number of sparse exponents e (which allow for fast RSA encryption) with the property that gcd(e,φ(M)) = 1 (hence RSA decryption can also be performed) is very close to the expected value.