A pseudo-random number generator is a deterministic function that produces a complex sequence of values that should be hard to distinguish statistically from a true random sequence. The sequence is usually defined iteratively, with

xn+1 = f( xn )

with perhaps some hidden state information, sn, so

(xn+1, sn+1) = f( xn, sn )

  1. The multiplcative (or linear) congruential generator is defined by

    xn+1 = a * xn + b mod M

    For example, lrand48() (available on our Unix systems) is defined by a = 2736731631558, b = 138, and M = 248

  2. The power generator is defined by

    xn+1 = xnd mod N

    Special case: if N is the product of two primes, this is called the RSA generator, and the randomness of the bits is related to the security of the RSA public-key cryptosystem, which depends on the difficulty of factoring N.

  3. The discrete exponential generator is defined by

    xn+1 = g xn mod N

    If N is prime and g is a generator (so all integers between 0 and N-1 are obtained as powers of g mod N) then the randomness of this generator depends on the difficulty of the discrete logarithm problem. This generator is related to the Diffie-Hellman key exchange protocol.

  4. The kneading map is defined by

    (xn+1, yn+1) = (yn, xn + f( yn, zn) )

    The z values are often constant or a repeating series of values. This is related to the DES cryptosystem.This can be inverted (even if f cannot) by

    (xn, yn) = (xn+1 - f( xn+1, zn), xn+1 )