Blum–Micali algorithm

The Blum-Micali algorithm is used as a pseudo random generator in cryptography. The algorithm gets its security from the difficulty of computing discrete logarithms.

$\mathbf {Let\ } g\mathbf {\ be\ prime}$ $\mathbf {Let\ } p\ \mathbf {be\ an\ odd\ prime}$

$X_{i+1}=g^{x_{j}}{\mbox{ }}mod{\mbox{ }}p$

It can be used to set bits since the output of the generator is either 0 or 1.

${\mbox{If }}X_{i}<{\frac {p-1}{2}}{\mbox{, then return }}1{\mbox{ else return }}0$

In order for this generator to be secure, the prime number p needs to be large enough so that computing discrete logarithms $mod{\mbox{ }}p$ is infeasible.

External links

• http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml