How do we test unpredictability?

Test suite

The unpredictability, i.e. the uniform distribution and the irreproducibility, of the random number sequences generated by HAVEGE was tested using the following packages:

Online analysis implementing the NIST statiscal suite is proposed as an option. Download HAVEGE library examples for details. You can also download an example of the NIST analysis output here.

Online analysis with NIST

The online testing we provide is derived from the NIST statistical suite for random number generator. For practical and theoretical description of the tests, the reader should consult the NIST report.

The minimum size of the sequence we analyze is 1 Mbyte and up to 256 Mbytes. Those tests were not originally written for analyzing such huge sequences of random numbers. Therefore, some performance gaps were encountered. Many tests were too CPU hungry and memory hungry to be run in a reasonable time (a few minutes for 1 Mbyte). We adapted those tests to run faster and with using less memory when possible. When despite our efforts, the response time was still too large, we run the test on a few "randomly" chosen subsequences.

NIST tests usage

  • Test 1: Frequency test.
  • Test 2: Block Frequency test.
  • Test 3: Runs test.
  • Test 14:Cumulative Sums.

Each of these tests are run on randomly selected subsequences for each of the size 128 bits, 256 bits, .. up to the complete sequence.

Test 4: Longest runs tests. We chose to 8 runs on randomly chosen 750000 bits sequences.

Test 5: Binary matrix rank test. This test is very CPU hungry. We chose to run it on only 8 randomly selected 38,192 bits sequences. and Test 4 (Longest runs tests)

Test 6: Discrete Fourier transfom. This test is very CPU hungry. We chose to run it on only 8 randomly selected 1Mbits sequences.

Test 7: Non Overlapping Template Matching. On a single randomly selected 1Mbits sequence, we run the 148 template matchings for templates of length 9.

  • Test 8: Overlapping Template Matching.
  • Test 10: Lempel-Ziv compression.
  • Test 12: serial test, m=14.
  • Test 15: Random Excursion.
  • Test 16: Random Excursion Variant.

We chose to run these tests on only 8 randomly selected 1000000 bits sequences.

Test 9: Maurer's Universal Tests. This test is run for all possible values higher than 6 on the beginning of the sequence.

Test 11: Linear Complexity. This test is the most CPU hungry of the collection. We chose to run it on a single randomly selected 4731*341 bits sequences.

Test 13: Approximate Entropy. We run this test for values from 3 to 16 on the whole sequence.

Note for Windows user:

You must have the Cygwin environment installed on Windows systems to run the NIST statistical suite.

We are interested in other uniform distribution tests and feedback on the generator. Please contact us.