

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

The Blum-Micali is a cryptographically secure pseudorandom number generator.

The construction (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.

I have toyed with small values of $p$ and have noticed that cycles occur if there's a fixed point, that is $x_{i+1} = x_i = g^{x_i}$.

For example when $g=3$ and $p=7$ (from wikipedia primitive root example), there are two fixed points where $3^4 = 4 \bmod 7$ and $3^5 = 5 \bmod 7$. This would be problematic for Blum-Micali generator since it would cycle and repeatedly output the same bit.

Is there a relationship with the size of $p$ and the period which is based on the likelihood of a fixed point?

share|improve this question
Interesting question. The heuristic argument is obvious but I'd be interested in seeing some real (i.e. non-generic) analysis of the properties of $x \mapsto g^x \mod{p}$. Searching for "discrete logarithm fixed point" I found some references, but they all seem to focus on describing the set of primes and primitive roots with at least one fixed point, rather than a lower bound on the number of fixed points for any given $p$. – Thomas Apr 7 '14 at 7:41
The premise seems faulty. Cycles can occur even if there is no fixed point. So, focusing on fixed points seems mis-placed, if you really care about cycles. But, as I explain in my answer, worrying about short cycles is also mis-placed concern. – D.W. Apr 7 '14 at 8:50

Since Blum-Micali is cryptographically secure, you know that there won't be a short cycle (not one short enough to detect in polynomial time), because a short cycle would violate cryptographic security. Therefore, you don't need to worry about this. It's not worth your time worrying about it: it's very unlikely you'll run into a short cycle.

That said, why do you want to use Blum-Micali? I wouldn't recommend it for any practical application. Instead, I'd recommend something like AES-CTR.

share|improve this answer
Regarding the last sentence, how exactly did you arrive at the conclusion that the OP wanted to use Blum-Micali? Seems to me he was only curious about the implications of fixed points in the permutation function. – Thomas Apr 7 '14 at 10:48

Your Answer


