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$.