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 &lt; \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?
Under the question's hypothesis, $x\mapsto g^x\bmod p$ is a permutation of $\mathbb Z_p^*$, that has some characteristics of being random.

If we take a random permutation of a set of size $s$, the length of the cycle iterating that permutation from a random point has length $l$ with probability exactly $1/s$, independent of integer $l$ with $1\le l\le s$. It follows that the cycle has length $l$ or less with probability exactly $l/s$.

This forms an heuristic argument (obvious, as pointed by Thomas in comment) that perhaps it is $\epsilon$-rare that the cycle length of the question's generator is much less than $\epsilon\,p$.

This is however very far from a proof or even a convincing argument. In particular, because $x\mapsto g^x\bmod p$ belongs to a very small and special subset of the permutations of $\mathbb Z_p^*$, with that subset having $(p-1)/2$ elements out of $(p-1)!$ permutations.

By contrast, D.W.'s argument is a valid proof that the cycle length is too large to be found when $p$ is such that the discrete logarithm problem is hard. However that gives a considerably looser safe estimate of the cycle length; perhaps likely at least $2^{100}$ for $2048$-bit randomly-seeded $p$, when the above heuristic argument suggests likely at least $2^{2040}$.