Types of Pseudo Random Number Generators

Linear congruential generators (LCG): As per Stephen Wolfram of the website Wolfram Demonstration Project:

"An LCG generates pseudorandom numbers by starting with a value called the seed, and repeatedly applying a given recurrence relation to it to create a sequence of such numbers."

This means that a sequence is created wherein the second term, is the function of the seed, the third term is a function of the first (a function of the function of the seed), and the third is a function of the second, ad infinitum. Because of this, sequences produced by LCGs often exhibit autocorrelation. Lagged Fibonacci generators (LFG) are the same as an LCG except each term in the sequence is the sum of the last two terms in the sequence, which exhibits higher evidence of randomness compared to traditional LCGs.

Generalized Feedback Shift Register: A shift register is a group of electronic circuits arranged so that data is shifted from one adjacent circuit to another, and then out. The seed of an LFSR is its initial state; it then builds a sequence based first on functions of the seed, and then on functions of the previous value of the sequence. These sequences have long periods, but share some of the key properties of random numbers. According to T.G. Lewis and W.H. Payne:

"The generalized feedback shift register pseudorandom number algorithm has several advantages over all other pseudorandom number generators. These advantages are: (1) it produces multidimensional pseudorandom numbers; (2) it has an arbitrarily long period independent of the word size of the computer on which it is implemented; (3) it is faster than other pseudorandom number generators; (4) the "same" floating-point pseudorandom number sequence is obtained on any machine, that is, the high order mantissa bits of each pseudorandom number agree on all machines- examples are given for IBM 360, Sperry-Rand-Univac 1108, Control Data 6000, and Hewlett-Packard 2100 series computers; (5) it can be coded in compiler languages (it is portable); (6) the algorithm is easily implemented in microcode and has been programmed for an Interdata computer."

Linear Feedback Shift Registers (LFSR) simply use linear functions to build the sequence. The seed of an LFSR is its initial state; it then builds a sequence based first on linear functions of the seed, and then on linear functions of the previous vale of the sequence. Like GFSRs, these sequences have long periods, but share some of the key properties of random numbers.

Mersenne twister: The period of the random number sequence generated by this algorithm is always a Mersenne prime, which is a prime number categorized by the form M_n = 2ⁿ - 1. This algorithm produces extremely low levels of autocorrelation, and passes a number of statistical tests for randomness. However, the twister can take some time to turn into random output if the seed is non-random.

The previous PRNGs lend themselves well to simulation, but there are a few that lend themselves well to cryptography because they are harder to manipulate. Fortuna is a series of PRNGs made especially for cryptography that introduces genuine random data (from an RNG) into the function that generates the sequence from the seed. The RNG makes this a very secure PRNG because an infiltrator could not compromise the random element. Blum Blum Shub is an algorithm based on a recursive relation concerning the product of primes. It is very slow and therefore not ideal for simulations, but the algorithm has certain mathematical properties that make it difficult to manipulate, and thusly attractive to cryptographers.

Sources

Joe Bolte, Linear Conguential Generators, Wolfram Demonstration Project

Summary and Recommendations, Computational Science Education Project

Linear Feedback Shift Registers, Mac HomePage

T.G. Lewis and W.H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM