# 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?