Ilja Gerhardt - Random Number Tests

Random Number Testing

Random numbers are important in our everyday life. They are needed for gambling, statistical testing (Monte-Carlo methods) and, most important, for encryption. Theoretically random numbers are infinitely long. But if you have a part of such a number in front of you, it's very hard to judge if it's a part of a 'good' or a 'bad' random number - so a variety of clever people developed tests for random numbers. Most of these tests for random numbers are available out on the internet. These tests verify a number of assumptions, which should be fulfilled if you are dealing with a good random number. Normally you (or at least an average human being) assume the following things:

The random number is balanced, it has the same number of 1s and 0s.
The n+1 bit can not be predicted by knowing the 0..n's bits.

The following statistical test suites exist on the internet. Quite a few are based on the discussions by Donald Knuth in his book "The Art of Computer Programing" [1]. Another good introduction to random numbers and their testing can be found in [2].

Please note that a variety of tests are appearing in several testsuites. It is also important to realize that one should be careful, because the test has ideally to be tailored to the specific problem, which it is testing for. In the following I implemented the NIST test suite in to two other languages (Mathematica and Python), to be flexible how to use them.

The NIST testsuite as Mathematica

This extends the work of Nick Galbreath, who did a first implementation in Mathematica, which was unfortunately very buggy. I enjoyed the code nevertheless and it helped me to understand what each test is doing. Also it might be convenient to include the code into an existing framework of the computer algebra system. The code is simple, but has a few nice extensions, which do the following things:

Generate the first 1000000 digits of Pi, E, Sqrt[2] and Sqrt[3] to test it against the NIST documentation.
The code is tested against these documented values. All values are matching the described values in section B of the NIST documentation.
Each test is timed and shows the inefficiency of Mathematica against other languages.
The code also allows to plot a nice result to a random number test, which might be publishable. See an example below.
I don't know why, but a lot of people like to display their random numbers somehow, I added a matrix of black and white pixels to display the binary expansion of pi.

And, of course, since the code is written in Mathematica, it has all the drawbacks Mathematica brings in. Mainly the code is slow. Since I based my work on the trial of Nick Galbreath, the code retains the BSD-license.

Download the Mathematica code here. It is tested for Mathematica 7 and 8.

The NIST testsuite in Python

Since Python is quick and tends to be better suited to handle large bitstreams, I adapted the entire NIST suite to python as well.

The package contains a module (randtest.py) and a wrapper script (testrandom.py), which utilizes 'argparse' to make it a nice command line tool.
The usage is straight forward:

$ ./testrandom.py --help
usage: testrandom.py [-h] [-i INFILE] [-o OUTFILE] [-t [TESTS [TESTS ...]]]
                     [-b] [-c] [-m] [-j] [-e] [-s] [-x] [-v]

        Evaluate the input for randomness 
        NIST Test Suite
        see: http://csrc.nist.gov/rng/

optional arguments:
  -h, --help            show this help message and exit
  -i INFILE, --infile INFILE
                        the file from where the random number should be
                        read(default: read from stdin)
  -o OUTFILE, --outfile OUTFILE
                        the file where the result should be written (default:
                        write the result to stdout)
  -t [TESTS [TESTS ...]], --tests [TESTS [TESTS ...]]
                        which tests to run, default: all
  -b, --binary          read in binary file
  -c, --comma           separate result with comma
  -m, --mathematica     prepare for Mathematica input
  -j, --join            read from a text file and join the lines
  -e, --evaluate        evaluate if Random or not (True/False)
  -s, --summarize       evaluate & summarize if Random or not (True/False)
  -x, --explanations    show a header of these runs
  -v, --version

if you want, you can simply send in a binary random string to the program:

$ echo "110010111001001" | ./testrandom.py -t 1
0.796253414738

you can also add a header line, simply by adding '-x'

$ echo "110010111001001" | ./testrandom.py -x -t 1
# monobitfrequencytest
0.796253414738

The Python code can be downloaded here. It is tested for Python 2.66.

[1] Donald E. Knuth, Art of Computer Programming, Addison-Wesley Professional
[2] Alfred Menezes, Paul van Oorschot, Scott Vanstone, Handbook of Applied Cryptography (Discrete Mathematics and Its Applications), CRC Press

Contact