On the Number of Solutions of Exponential Congruences

Abstract

For a prime $p$ and an integer $a\in \mathbb{Z}$ we obtain nontrivial upper bounds on the number of solutions to the congruence $x^x\equiv a(\mathrm{mod}p)$, $1\le x\le p-1$. We use these estimates to estimate the number of solutions to the congruence $x^x\equiv y^y(\mathrm{mod}p)$, $1\le x,y\le p-1$, which is of cryptographic relevance.