# 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.

^{[1]}

Let be an odd prime, and let be a primitive root 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.^{[1]} 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.^{[2]}

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.^{[3]}

## References

- ↑
^{1.0}^{1.1}Bruce Schneier,*Applied Cryptography: Protocols, Algorithms, and Source Code in C*, pages 416-417, Wiley; 2nd edition (October 18, 1996), ISBN 0471117099 - ↑ Manuel Blum and Silvio Micali,
*How to Generate Cryptographically Strong Sequences of Pseudorandom Bits,*SIAM Journal on Computing 13, no. 4 (1984): 850-864. online (pdf) - ↑ Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr, Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction http://arxiv.org/abs/1012.1776