# Short Cycles in Repeated Exponentiation Modulo a Prime

Authors
Type
Preprint
Publication Date
Aug 27, 2009
Submission Date
Aug 27, 2009
Identifiers
arXiv ID: 0908.3920
Source
arXiv
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 \pmod 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.