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 safety-measures 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 safety-measure 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 number-theoretic 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 full-period 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 explicit-inversive 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 de-facto 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. Addison-Wesley, Reading, MA, 3rd edition, 1997.

back to the top

Research supported by