x_{n+1} = f( x_{n} )

with perhaps some hidden state information, s_{n}, so

(x_{n+1}, s_{n+1}) = f( x_{n}, s_{n} )

- The
**multiplcative (or linear) congruential generator**is defined byx

_{n+1}= a * x_{n}+ b mod MFor example, lrand48() (available on our Unix systems) is defined by a = 2736731631558, b = 138, and M = 2

^{48} - The
**power generator**is defined byx

_{n+1}= x_{n}^{d}mod NSpecial 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.

- The
**discrete exponential generator**is defined byx

_{n+1}= g^{xn}mod NIf 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.

- The
**kneading map**is defined by(x

_{n+1}, y_{n+1}) = (y_{n}, x_{n}+ f( y_{n}, z_{n}) )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

(x

_{n}, y_{n}) = (x_{n+1}- f( x_{n+1}, z_{n}), x_{n+1})