0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.