ABOUT THIS PAGE
On this page, you will find information on tests for uniform random
number generators (RNGs). We will not discuss testing nonuniform
random numbers.
For code,
we refer to the
TESTU01 library of L'Ecuyer and Simard (Montreal University).
This page has been written by Peter
Hellekalek.
GENERAL REMARKS
Fact one: With random number generators (RNGs), there are no guarantees.
We can only predict what will happen in practice.
This is not because the word ''randomness'' is involved but because
the finitely many random numbers we produce and their transformed
variates cannot fit every imaginable distribution well enough.
Every generator has its regularities which, ocassionally, may become
deficiencies. Hence, in a given application, even reliable generators
may fail.
In cryptographical appplications,
the unpredictability of the output is an additional,
very important requirement.
It is difficult to construct RNGs that are at the same time efficient
and cryptographically secure.
We refer to the
eSTREAM
project for further information on the construction and cryptanalysis of
various stream ciphers.
Fact two: Although there are no guarantees, there are mathematical
safetymeasures against wrong simulation results due to inappropriate
random number generators.
There are also mathematical safety measures against cryptanalysis.
We will dwell upon this topic in a later version of this page and refer
to the
Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone
instead.
One safetymeasure is to assess generators by theoretical tests,
the other is to submit them to empirical (``statistical'') tests.
Of course, it is preferable that the latter are related to our simulation
problem or to our cryptographical application.
In the case of RNGs in stochastic simulation, most of the commonly
used algorithms may be analyzed theoretically. We use concepts like
discrepancy or the spectral test to study correlations within the
output stream of the RNG. Discrepancy cannot be computed in higher
dimensions (i.e. dimensions above 2), its computational complexity
is too high. One resorts to discrepancy estimates, which are obtained
by numbertheoretic methods developped by Harald Niederreiter et al.
In order to give you an idea of this approach,
we will present a little table for this kind of theoretical results,
see
Theoretical Tests.
Discrepancy estimates for a given linear congruential generator (LCG)
are not known,
only results in the mean over all fullperiod multipliers
for a given modulus are available.
These facts are indicated by the ,+ and + signs in the table.
In sharp contrast,
for given inversive congruential generators (ICG) and
explicitinversive congruential generators (EICG),
the discrepancy can be estimated.
The spectral test
is the most important test to select good parameters
for linear types of RNGs like LCGs and multiple recursive generators (MRG).
The spectral test is very efficient,
but it requires RNGs that generate lattice structures in higher dimensions.
It assesses lattices and is also of importance in certain areas of
cryptography.
Hence, it is not defined for nonlinear generators like ICGs and EICGs.
The quality of RNGs depends strongly upon the choice of parameters.
In general,
inversive generators are less sensible in this respect
and offer a wider choice of good parameters than linear algorithms.
Of course, the situation is different when it comes to efficiency.
In our table
Empirical Tests below,
we would like to give you an idea how sensible the choice of parameters is.
In the case of cryptographic RNGs, the situation is usually much
more difficult. For most cryptographic RNGs, their algorithms will
be too complicated to yield to theoretical analysis. It will be
out of question to use discrepancy estimates or to compute something
like the spectral test for these RNGs. Therefore, in such cases
only an empirical (statistical) analysis of sample output will be
possible.
THEORETICAL TESTS
The most difficult and most important topics
in the theoretical assessment of random number generators
are correlation analysis and,
for cryptographic RNGs,
the analysis of their unpredictability.
More than twenty years of experience have shown that certain figures
of merit (also known as ``theoretical tests'') for random number
generators allow very reliable predictions of the performance of
the samples produced with a generator in empirical tests.
The latter are nothing less than prototypes of simulation problems.
Hence, the importance of theoretical correlation analysis for numerical
practice is beyond question.
It should be stated clearly that none of these figures of merit
can give us guarantees for the performance of the generator in our
simulation.
At present, there is no firm mathematical link between any figure
of merit for random number generators and the empirical performance
of samples. Nevertheless, and this fact is truly remarkable, the
quality of prediction is excellent.
The most important figures of merit for this task are discrepancy
and the spectral test, and a newcomer, the weighted spectral test,
also known as diaphony.
For cryptographic RNGs,
in most cases,
these figures of merit are useless.
RNGs as they are used in cryptographic applications
are much too complicated to allow for this kind of
(number) theoretical analysis.
There is too little structure in the output streams to
carry out this kind of theoretical analysis.
EMPIRICAL TESTS
Theoretical support for random number generators is not enough.
Theoretical assessment of random number generators cannot guarantee
good performance of the samples in numerical practice, it can only
give a (remarkably reliable) forecast of what will happen.
The same statement is true for the security of cryptographic RNGs.
We cannot guarantee security of a given algorithm.
Empirical evidence is indispensable.
Every empirical test is a simulation. If selected with care, then
a particular test will cover a whole class of simulation problems.
Nothing can be deduced from the results of an empirical test if
the practitioner uses completely different parameters in his own
simulation problem. In contrast to theoretical tests, empirical
tests treat the random number generators as black boxes and do not
directly analyze the underlying algorithm. This makes it possible
to observe the performance for smaller and larger parts of the period.
In cryptography,
as soon as we can distinguish a given bitstream from the output of
a "perfect random source",
attacks to the algorithm will be possible.
The difficulty is to find such distinguishers and to mount an efficient attack.
The most exiting development in the field of statistical testing
in the last few years has been the publication of the
TESTU01
battery of
Pierre L'Ecuyer and Richard Simard (Montreal University, Canada).
TESTU01 comprises practically all statistical tests that have been designed
so far.
A most helpful feature for any practioner are several libraries of predefined
tests that can be used to check the output of an RNG.
Historically,
there were other widely used test batteries,
the famous DIEHARD battery
of George Marsaglia,
which has been a defacto standard with practitioners for many years,
and the NIST
battery of the National Institute of Standards and Technology for
cryptographic RNGs.
Underlying all these batteries is Donald Knuth's famous
collection of tests, see
The Art of Computer Programming, volume 2:
Seminumerical Algorithms. AddisonWesley, Reading, MA, 3rd edition, 1997.
back to the top
Research supported by
