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

Cryptographically secure pseudorandom number generator

A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...

. The algorithm gets its security from the difficulty of computing discrete logarithms.

Let be an odd prime, and let be a primitive root

Primitive root modulo n

In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n...

modulo . Let be a seed, and let
.

The th output of the algorithm is 1 if
.
Otherwise the output is 0.
In order for this generator to be secure, the prime number needs to be large enough so that computing discrete logarithms modulo is infeasible. To be more precise, any method that predicts the numbers generated will lead to an algorithm that solves the discrete logarithm problem for that prime

There is a paper discussing possible examples of the quantum permanent compromise attack to the Blum-Micali construction. This attacks illustrate how a previous attack to the Blum-Micali generator can be extended to the whole Blum-Micali construction, including the Blum-Blum-Shub and Kaliski generators.