## FANDOM

567 Pages

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

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.[1] To be more precise, if this generator is not secure then there is an algorithm that computes the discrete logarithm faster than is currently thought to be possible.[2]

## References Edit

1. 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
2. Manuel Blum and Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864.