Blum–Micali algorithm

The Blum–Micali algorithm is a cryptographically secure pseudorandom number generator. The algorithm gets its security from the difficulty of computing discrete logarithms.

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   mod   p .

The i th output of the algorithm is 1 if x i < p − 1 2 . Otherwise the output is 0. This is equivalent to using one bit of x i as your random number. It has been shown that n − c − 1 bits of x i can be used if solving the discrete log problem is infeasible even for exponents with as few as c bits.

In order for this generator to be secure, the prime number p needs to be large enough so that computing discrete logarithms modulo p 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.