Distribution of powers modulo p and security of RSA
Xianmeng Meng, Yongjie Dang · Journal of Mathematical Cryptology · 2026
Abstract 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 ∈ Z p * : m − ( m a mod p ) < x , $$G\left(x\right)=\#\left\{m\in {\mathbb{Z}}_{p}^{{\ast}} : \left\vert m-\left({m}^{a} \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 ) = 2 x − x 2 p − 1 + O p 1 / 2 log 2 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 Ω N 3 / 4 log 3