# Is it possible to determine or estimate the period for Blum-Micali PRG?

The Blum-Micali is a cryptographically secure pseudorandom number generator.

The construction (from wikipedia):

• Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.

• Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ \bmod{\ p}$.

• The $i$-th output of the algorithm is 1 if $x_i < \frac{p-1}{2}$. Otherwise the output is 0.

I have toyed with small values of $p$ and have noticed that cycles occur if there's a fixed point, that is $x_{i+1} = x_i = g^{x_i}$.

For example when $g=3$ and $p=7$ (from wikipedia primitive root example), there are two fixed points where $3^4 = 4 \bmod 7$ and $3^5 = 5 \bmod 7$. This would be problematic for Blum-Micali generator since it would cycle and repeatedly output the same bit.

Is there a relationship with the size of $p$ and the period which is based on the likelihood of a fixed point?

-
Interesting question. The heuristic argument is obvious but I'd be interested in seeing some real (i.e. non-generic) analysis of the properties of $x \mapsto g^x \mod{p}$. Searching for "discrete logarithm fixed point" I found some references, but they all seem to focus on describing the set of primes and primitive roots with at least one fixed point, rather than a lower bound on the number of fixed points for any given $p$. – Thomas Apr 7 '14 at 7:41
The premise seems faulty. Cycles can occur even if there is no fixed point. So, focusing on fixed points seems mis-placed, if you really care about cycles. But, as I explain in my answer, worrying about short cycles is also mis-placed concern. – D.W. Apr 7 '14 at 8:50