1
$\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$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ So, can we have a general formula in regard of $p$, $g$ and $x_0$ ? $\endgroup$
    – BlueMango
    Commented May 22, 2020 at 16:04
  • $\begingroup$ 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$. $\endgroup$ Commented May 22, 2020 at 17:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .