I set out to find the state of the art in random number generation. It is more difficult than I expected. George Marsaglia is an expert in the field. One of his posts explains the problem and gives code for several good RNGs (latest versions of KISS, MWC256, and CMWC4096). He compares choosing the "best" random number generator to choosing the best in a "Miss America Contest". To be politically correct, I'll change his analogy to choosing the best automobile. If someone asked you which was the best car to get, how would you answer? The answer depends on the needs of the user. If he needs to move a lot of stuff around, you might recommend a pickup truck. If he needs to drive his family around, you might recommend an SUV, minivan, or 4-door sedan. Price and performance are also factors to consider. Then, there are the aesthetic issues. Which car, in terms of looks and design, is the most attractive to the user? So it goes on and on. And so it goes with random number generators.
The problem is that random number generators are not truly random. If you had access to a truly random source on your computer, you could just use that. Instead, you're trying to find an algorithm to generate random-looking numbers. As John von Neumann famously remarked, "Anyone who considers arithmetical methods of producing random numbers is, of course, in a state of sin." The quest is flawed from the start.
Generating random numbers for cryptography is very different than generating numbers for simulation. Most random number generators are designed to have good statistical properties; they are not designed to be unpredictable. I'm mainly concerned with RNGs with good statistical properties. For cryptographically secure random number generators, look at Yarrow, Blum Blum Shub, ISAAC, or one based on a secure digest or cipher. See, for example, Peter Gutmann's paper on Software Generation of Practically Strong Random Numbers. The Mersenne Twister FAQ also has suggestions for making it cryptographically secure.
The experts use the following criteria to measure a random number generator. See Pierre L'Ecuyer's Random Number Generation (2004, pdf) for a more thorough discussion of quality criteria.
Unfortunately, it depends on what you need it for. For simple uses, a well-designed linear congruential generator may be fine. If you need a cryptographically secure RNG, choose one that was designed to be secure (most RNGs weren't).
Ideally, you should test the RNG yourself. I list several test suites above. Even better is if you have statistical tests specific to how you will use the RNG. It's good to verify that the implementation you're using is good and that the RNG doesn't exhibit any biases when applied to your type of application.
There are dozens of very good RNGs. None is perfect, but none has obvious flaws. None is clearly superior to the others. How do you choose? It's as if you had chosen the best automobile for your needs and the salesman asks whether you want it to be black, silver, white, blue, or red. Which is best?
In Random Number Generation, L'Ecuyer recommends combined MRG's, combined LFSR's, and Mersenne twisters. GSL's Manual recommends several RNGs including Mersenne Twister. George Marsaglia has reservations about the complexity of Mersenne Twister, but considers it to be a good RNG nonetheless. The criticisms of Mersenne Twister tend to be aesthetic -- there are many simpler and faster RNGs with good foundations in theory which perform as well in statistical tests.
Although some experts may not like the aesthetic design of Mersenne Twister, I haven't seen any substantial criticisms. Matsumoto's Mersenne Twister seems to be a safe choice. It has strong support from people knowledgeable in the field, a good theoretical basis, a long period, good performance characteristics, and empirical statistical support.
[Last Modified: 9 June 2004]