Tests for Random Number Generators

Random number generation is the art of producing pure gibberish as quickly as possible. Block ciphers are similar; they take sensible stuff and turn it into gibberish as fast as possible. In both cases, we need very strict definitions of gibberish. Even the slightest pattern ("bias" in the jargon) cannot be tolerated. To detect such bias, we have a wide variety of tests.

Test results are usually reported as a chi2 measure. A chi2 measure of +-2 is probably random noise, +-3 probably means the generator is biased, and +-4 almost certainly means the generator is biased.

The best way to test if a generator is good enough for an application is to run the application with two very different generators and see if they produce the same result. The next best way is run the generator's random number sequence through random number tests, like DIEHARD or chi.c or est.c (described below). The sequence tested has to be at least as long as the sequence of random numbers your application plans to use, otherwise the biases your application may encounter can't be caught by the test.

An excellent test of random sequences is DIEHARD, maintained by George Marsaglia. You get it from http://stat.fsu.edu/~geo, or by ftp from stat.fsu.edu, login anonymous, cd pub, cd diehard, then get what you want. He has both executables and source code there.

I've got my own suite of random number tests that I wrote before I was able to locate DIEHARD. They can test sequences billions of values in length, and the sequences never need to be stored on disk. The program chi.c isn't very user-friendly or flexible, but it calculates the distributions for the frequency, gap, and run tests exactly, and once you compile in your random number generator it is very fast.

If chi.c doesn't have enough tests, try est.c. It estimates both the distribution and expected bias for arbitrary tests using a control random number generator. This makes test-writing much easier, and it lets you test sequences that aren't supposed to be uniform. You plug in your own control generator with some nonstandard distribution so you can test other sequences with the same distribution. I use est.c for exploration and debugging, and chi.c when I need test results I can publish. Theoretical justifications of est.c are here.

I developed these tests to break a generator, and I developed the generator to pass the tests. The generator is ISAAC. It passed the uni and gap tests in chi.c for sequences of 242 values. (Longer sequences haven't been tested; testing 242 values took two weeks.)


Random number results
Code for testing hash functions
A very strange key exchange protocol
Table of Contents