Short Cycles in Repeated Exponentiation Modulo a Prime

Abstract

Given a prime $p$, we consider the dynamical system generated by repeated exponentiations modulo $p$, that is, by the map $u\mapsto f_g(u)$, where $f_g(u)\equiv g^u(\mathrm{mod}p)$ and $0\le f_g(u)\le p-1$. This map is in particular used in a number of constructions of cryptographically secure pseudorandom generators. We obtain nontrivial upper bounds on the number of fixed points and short cycles in the above dynamical system.