# Is it possible to determine or estimate the period for Blum-Micali PRG?

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?

• 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

Under the question's hypothesis, $x\mapsto g^x\bmod p$ is a permutation of $\mathbb Z_p^*$, that has some characteristics of being random.

If we take a random permutation of a set of size $s$, the length of the cycle iterating that permutation from a random point has length $l$ with probability exactly $1/s$, independent of integer $l$ with $1\le l\le s$. It follows that the cycle has length $l$ or less with probability exactly $l/s$.

This forms an heuristic argument (obvious, as pointed by Thomas in comment) that perhaps it is $\epsilon$-rare that the cycle length of the question's generator is much less than $\epsilon\,p$.

This is however very far from a proof or even a convincing argument. In particular, because $x\mapsto g^x\bmod p$ belongs to a very small and special subset of the permutations of $\mathbb Z_p^*$, with that subset having $(p-1)/2$ elements out of $(p-1)!$ permutations.

By contrast, D.W.'s argument is a valid proof that the cycle length is too large to be found when $p$ is such that the discrete logarithm problem is hard. However that gives a considerably looser safe estimate of the cycle length; perhaps likely at least $2^{100}$ for $2048$-bit randomly-seeded $p$, when the above heuristic argument suggests likely at least $2^{2040}$.

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.

• 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

What is often recommended is to make sure that your value of g is a "generator" mod p. I don't know if this term is often used, but I've had it defined as cycling through the entirety of a set {0, 1, ..., p - 1} by raising it to consecutive powers mod p. If you use a number with this property, you will never have any short cycles and will in fact generate every value available mod p.

• This doesn't really seem to answer the question. – Maeher Feb 5 '18 at 11:10
• $g$ is a generator if and only if $x\mapsto g^x\bmod p$ is a permutation. But permutations can have short cycles, hence it does not follows from $g$ being a generator that the construction in the question has maximum cycle; and experiment (as pointed by the question) shows otherwise. Further, the problem statement has "let $g$ be a primitive root modulo $p$", which means $g$ is a generator, thus this answer's recommendation is already part of the problem statement. – fgrieu Feb 5 '18 at 14:09