# When will the random bit sequence start to repeat in pseudo random number generator

Let's say we have the Blum-Micali pseudorandom number generator.

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.

When will the random bits generated start repeating in this case? I have manually tried some examples but could not find a pattern there.

• For p = 19, g = 3, $$x_o$$ = 4, bit sequence start repeating after 10 bits
• For p = 19, g = 3, $$x_o$$ = 3, bit sequence start repeating after 8 bits
• For p = 7, g = 3, $$x_o$$ = 3, bit sequence start repeating after 3 bits
• For p = 11, g = 6, $$x_o$$ = 4, bit sequence start repeating after 4 bits
• For p = 11, g = 6, $$x_o$$ = 9, bit sequence start repeating after 6 bits

Is there a relationship with the size of $$p$$, $$g$$ and $$x_0$$ and the period when the bits start repeating themselves?

If you're unlucky in your choice of $$p, g, x_0$$, you might even have a period of $$1$$. For example, $$2$$ is a primitive root mod $$13$$, and $$2^{10} \equiv 10 \mod 13$$.
• So, can we have a general formula in regard of $p$, $g$ and $x_0$ ? Commented May 22, 2020 at 16:04
• I don't think there's a simple formula. I think that for large primes $p$, most primitive roots $g$ will have some $x_0$ such that $g^{x_0} \equiv x_0 \mod p$. Commented May 22, 2020 at 17:24