Short cycles in repeated exponentiation modulo a prime.

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) ≡ g ^u (mod p) and 0 ≤ f _g( u) ≤ 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. [ABSTRACT FROM AUTHOR]