Short cycles in repeated exponentiation modulo a prime (Q977189)

Given a prime \(p\) and an integer \(g\) with gcd\((g, p) = 1\) one can consider the dynamical system generated by consecutive exponentiations modulo \(p\) where \(g\) serves as the base. More precisely, one can define the map \(f_g(u)\) by the conditions \(f_g(u) \equiv g^u\) (mod \(p\)) and \(0 \leq f_g(u) \leq p - 1\), and for some initial value \(u_0\) consider sequences of consecutive iteration \(u_n = f_g(u_{n-1}), n = 1, 2, \cdots\). This map is in particular used in a number of constructions of cryptographically secure pseudorandom generators. For an integer \(k\) one denotes by \(N_g(k)\) the number of \(u_0 \in {1,\cdots , p-1}\) such that for the above sequence we have \(u_k = u_0\). The authors obtained nontrivial upper bounds on the number of fixed points and short cycles in the above dynamical system, they proved, among other things, the following: Theorem. Let \(p\) be a prime. Then \(N_g(3) \leq \frac{3}{4}p + (\frac{g^{2g+1}+g+1}{4})\).