The Blum-Micali algorithm is a cryptographically secure pseudorandom number generator. The algorithm gets its security from the difficulty of computing discrete logarithms.
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. 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.
- ↑ 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.