Fandom

DSZQUP XJLJ

Blum-Micali algorithm

566pages on
this wiki
Add New Page
Talk0 Share

Template:Orphan

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

External links Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.