Distribution of powers modulo p and security of RSA

Let p be a prime and a be any fixed positive integer such that gcd(a, φ(p)) = 1. For 0 < x < p, define G(x)=#m∈Zp*:m−(mamodp)<x, $$G\left(x\right)=\#\left\{m\in {\mathbb{Z}}_{p}^{{\ast}} : \left\vert m-\left({m}^á} \mathrm{mod} p\right)\right\vert {< }x\right\},$$ where m a mod p is the least nonnegative residue of m a modulo p. We prove that G(x)=2x−x2p−1+Op1/2⁡log2⁡p. $$G\left(x\right)=2x-{x}^{2}{p}^{-1}+O\left({p}^{1/2}{\mathrm{log}}^{2}p\right).$$ This distribution result has an immediate cryptographic consequence. For RSA having public key N,e $\left(N,e\right)$ with small exponent e (such as 3 or 65537), we show that there exist at least ΩN3/4⁡log3⁡N ${\Omega}\left({N}^{3/4}{\mathrm{log}}^{3}N\right)$ special plaintext–ciphertext pairs from which N can be factored in time O(log12 N).