On the number of sparse RSA exponents (Q701120): Difference between revisions

RSA is a method proposed by \textit{R. L. Rivest}, \textit{A. Shamir} and \textit{L. Adleman} [Commun. ACM 21, 120--126 (1978; Zbl 0368.94005)] to encrypt and sign electronically. In the scheme, an integer \(x\) modulo \(M=pl\) where \(p\) and \(l\) are prime, is raised to a certain power \(e\), where \(\gcd (e,\varphi(M))=1\). For efficiency reasons, sparse exponents \(e\) have been proposed. This paper studies the distribution of such exponents coprime to \(\varphi(M)\) having exactly \(k\) entries in their binary expansion. Using sieving methods as developed by \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith. 81, 145--173 (1997; Zbl 0887.11008)] the authors show that the number \(N_{n,k}(M)\) of such \(e\) of binary length at most \(n\) is close to the expected value of \(V_{n,k}=2{{n-1}\choose{k-1}}\frac{\varphi(\varphi(M))}{\varphi(M)}\). This is done by proving that the average value of \(N_{n,k}(M)-V_{n,k}\) over all RSA moduli \(M\) of exact length \(n\) can be bounded by \(O(kn^3{{n-1}\choose{k-1}}\exp(-ck^{3/2}n^{-1}))\) for some absolute constant \(c\).