Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 at 7:41
1  
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 at 8:50

1 Answer 1

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
1  
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 at 10:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.