- Home
  - Contact
  - Impressum
Home

About us
Generators
Links
Literature
- Introductions
- Foundations
- Simulation
- Cryptography
Software
Tests
 
INTRODUCTIONS & SURVEYS
In the context of stochastic simulation (i.e. Monte Carlo methods), the current state of the art in random number generation is reflected in the proceedings of the Monte Carlo and Quasi-Monte Carlo (MCQMC) conferences, see the website www.mcqmc.org. The latest issues in this series of proceedings are
Fang, K.-T., Hickernell, F.J., and Niederreiter, H. (editor):Monte Carlo and Quasi-Monte Carlo Methods 2000. Springer-Verlag, New York, 2002.

Niederreiter, H. and Spanier, J. (editor): Monte Carlo and Quasi-Monte Carlo Methods 1998. Springer-Verlag, New York, 2000.

There are three books that constitute a "survival kit" for this field, by Knuth, Niederreiter, and Hörmann, Leydold, and Derflinger. The "bible", i.e. an all-time classic in the field of random numbers is

Knuth, D.E.: The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 3rd edition, 1997.

Knuth's book is extremely rich in information but requires good knowledge of mathematics, in particular number theory. I would not recommend this book as first reading for practitioners. The following monograph contains a comprehensive discussion of the theoretical assessment of random number generators and a valuable list of references. Readers should be prepared for a text in pure mathematics, in particular number theory and algebra (theory of finite fields).

As Knuth's book, Niederreiter's excellent monograph is an important reference in this field.
Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, 1992.

The monograph on nonuniform random variate generation,

Hörmann, W., Leydold, J. and Derflinger, G.: Automatic Nonuniform Random Variate Generation. Springer-Verlag, New York, 2004,

will be very helpful for all those who need nonuniform random numbers.

The following papers of Pierre L'Ecuyer survey many of the basic concepts and results of random number generation, most of it readable by non-specialists. I strongly recommend to visit Pierre's webpage for his latest results.
L'Ecuyer, P.: Uniform random number generation. Ann. Oper. Res., 53: 77--120, 1994.

L'Ecuyer, P.: Random number generation. In Jerry Banks, editor(s), The Handbook of Simulation, pp. 93--137. Wiley, New York, 1998.

L'Ecuyer, P.: Random number generation. Draft for a chapter of the forthcoming Handbook of Computational Statistics, J. E. Gentle, W. Haerdle, and Y. Mori, eds., Springer-Verlag, 2004.

his paper of mine was written for practitioners. It explains the state of the art to assess random number generators and gives pointers to implementations of the latest advances in generating random numbers up to 1999.

Hellekalek, P.: Good random number generators are (not so) easy to find. Mathematics and Computers in Simulation, 46: 485--505, 1998.

The first twenty pages of the following contribution deal with the importance of theoretical (i.e. a priori) testing of RNGs, illustrated by examples, and written in a language easily understood by practitioners.

Hellekalek, P.: On the assessment of random and quasi-random point sets. In Hellekalek, P. and Larcher, G., editor(s), Random and Quasi-Random Point Sets of Lecture Notes in Statistics. Springer-Verlag, New York, 1998.

If you are looking for a compact survey of the theoretical properties of random number generators, with a special interest in nonlinear types, then an excellent source is

Niederreiter, H.: New developments in uniform pseudorandom number and vector generation. In Niederreiter, H. and Shiue, P.J.-S., editor(s), Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, volume 106 of Lecture Notes in Statistics. Springer-Verlag, Heidelberg New York, 1995.

The following paper contains a concise survey of the performance of inversive random number generators in theoretical and empirical tests, as well as tables of parameters to implement inversive generators.
Hellekalek, P.: Inversive pseudorandom number generators: concepts, results, and links. In Alexopoulos, C. and Kang, K. and Lilegdon, W.R. and Goldsman, D., editor(s), Proceedings of the 1995 Winter Simulation Conference, pp. 255--262. , 1995. Abstract available.

For those who want to understand the goals and the limitations of empirical testing of random number generators (and why undefined notions like "independence of random numbers", and "statistical properties of numbers" should be avoided), there is a Master's thesis dedicated to these questions, written by Stefan Wegenkittl. It also contains comprehensive results on Marsaglia's M-tuple test for inversive and linear generators.
Wegenkittl, S.: On Empirical Testing of Pseudorandom Number Generators. In De Pietro,G. and Giordano, A. and Vajtersic, M. and Zinterhof, P., editor(s), Proceedings of the international workshop Parallel Numerics '95. CEI-PACT Project, WP5.1.2.1.2. , 1995.

Stefan has recently published a very interesting addition to Maurer's universal statistical test for random bit generators, see
Wegenkittl, S.: Entropy Estimators and Serial Tests for Ergodic Chains. IEEE Transactions on Information Theory, 47: (6) 2480--2489, 2001.

Additional interesting surveys of the field are given in the papers below, sorted by date of publication. The surveys of Anderson, Marsaglia, and L'Ecuyer are of particular interest for practitioners.

Marsaglia, G.: A current view of random number generators. In Billard, L., editor(s), Computer Science and Statistics: The Interface, pp. 3--10. Elsevier Science Publishers B.V., Amsterdam, 1985.

Anderson, S.L.: Random number generators on vector supercomputers and other advanced architectures. SIAM Rev., 32: 221--251, 1990.

Eddy, W.F.: Random number generators for parallel processors. J. Comp. Appl. Math., 31: 63--71, 1990.

L'Ecuyer, P.: Random numbers for simulation. Comm. ACM, 33: 85--97, 1990.

L'Ecuyer, P.: Random number generation. In Jerry Banks, editor(s), The Handbook of Simulation, pp. 93--137. Wiley, New York, 1998.

Ripley, B.D.:Thoughts on pseudorandom number generators. J. Comput. Appl. Math. , 31: 153--163, 1990.

 

MATHEMATICAL FOUNDATIONS AND PHILOSOPHY
How to define the notion of "a (finite) sequence of random numbers"? Knuth describes the problem as this:

The mathematical theory of probability and statistics carefully sidesteps this question; it refrains from making absolute statements, and instead expresses everything in terms of how much probability is to be attached to statements involving random sequences of events. The axioms of probability theory are set up so that abstract probabilities can be computed readily, but nothing is said about what probability really signifies, or how this concept can be applied meaningfully to the actual world.
The following papers and textbooks propose notions of randomness different from Kolmogorov's:
Chaitin, G.J.: Randomness and mathematical proof. Sci. Amer., 232: 47--52, 1975.

Compagner, A.: Definitions of randomness. Am. J. Phys., 59: 700--705, 1991.

Kac, M.: What is random?. American Scientist, 71: 405--406, 1983.

Knuth, D.E.: The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 2nd edition, 1981.

Schnorr, C.P.: Zufälligkeit und Wahrscheinlichkeit, volume 218 of Lecture Notes in Math.. Springer, Berlin, 1971.

The theory of uniform distribution of sequences, a sub field of number-theory, is not concerned with randomness but provides highly useful tools to construct theoretical "figures of merit" for random number generators. The keyword is "discrepancy of point sets and sequences". For an excellent introduction to this field, see
Kuipers, L. and Niederreiter, H.: Uniform Distribution of Sequences. John Wiley, New York, 1974.

Even the spectral test is nothing else than a measure of uniform distribution, as I have shown in my survey
Hellekalek, P.: On the assessment of random and quasi-random point sets. In Hellekalek, P. and Larcher, G., editor(s), Pseudo and Quasi-Random Point Sets of Lecture Notes in Statistics. Springer-Verlag, New York, 1998.

The algebraic background of random number generation (keyword: "arithmetics in finite fields"; think of shift register types of generators or of inversive generators) can be found in the comprehensive monograph
Lidl, R. and Niederreiter, H.: Finite fields. Addison-Wesley, Reading, Mass., 1983.

There is a monograph on the Monte Carlo method that will certainly become a standard reference, in particular among practitioners,

Fishman, G.S.: Monte Carlo: Concepts, Algorithms, and Applications. Springer-Verlag, New York, 1996.

The same holds for the monograph on nonuniform random variate generation,

Hörmann, W., Leydold, J. and Derflinger, G.: Automatic Nonuniform Random Variate Generation. Springer-Verlag, New York, 2004.

 

SIMULATION
LINEAR GENERATORS
This type of generator is the best-known (and analyzed) approach to produce uniform random numbers. The spectral test (see our Spectral Test Server) is a very efficient figure of merit to assess linear generators like the linear congruential generator (LCG) or its generalization, the multiple recursive generator (MRG). There are many related methods. All these basic concepts are discussed in

L'Ecuyer, P.: Random number generation. In Jerry Banks, editor(s), The Handbook of Simulation, pp. 93--137. Wiley, New York, 1998.

Pierre L'Ecuyer is the leading specialist for this type of generators. He has driven the spectral test to new limits in efficiency, on the basis of the theoretical background provided by people like Ulrich Dieter, see
Dieter, U.: How to calculate shortest vectors in a lattice. Math. Comp., 29: 827--833, 1975.

and Donald Knuth (see his famous monograph cited above).

Among linear type generators, Matsumoto's twisted generalized feedback register generators (tGFSR) stand out. His "Mersenne Twister" is the current World Champion among random number generators, see

Matsumoto, M. and Kurita, Y.: Twisted GFSR generators. ACM Trans. Model. Comput. Simul., 2: 179--194, 1992.

Matsumoto, M. and Kurita, Y.: Twisted GFSR generators II. ACM Trans. Model. Comput. Simul., 4: 254--266, 1994.

Matsumoto, M. and Nishimura, T.: Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator . ACM Trans. Modeling and Computer Simulation, 8: 3--30, 1998.

A rather comprehensive collection of widly-used and also some exotic linear random number generators is due to my former student Karl Entacher. It is available on-line from our server. Karl's collection contains not only the parameters of these generators, but also the values of extensive spectral tests.

 

SIMULATION
NONLINEAR CONGRUENTIAL GENERATORS
Nonlinear random number generators constitute an important addition to the arsenal of algorithms for stochastic simulation practice. Their properties are radically different from those of linear generators. There are several theoretical and some practical advantages for nonlinear generators, like the absence of any lattice structure, but (currently) also two disadvantages: speed and period length. Nevertheless, these algorithms merit closer consideration in theory and in practice. The main designers of these algorithms are Harald Niederreiter and Jürgen Eichenauer-Herrmann. The most important nonlinear concept up to now is the so-called inversive congruential generator (ICG), due to Eichenauer-Herrmann and Lehn. A survey of inversive random number generators is given in

Hellekalek, P.: Inversive pseudorandom number generators: concepts, results, and links. In Alexopoulos, C. and Kang, K. and Lilegdon, W.R. and Goldsman, D., editor(s), Proceedings of the 1995 Winter Simulation Conference, pp. 255--262. , 1995. Abstract available.

This paper contains a concise discussion of the main concepts of generating and testing inversive random numbers and a comparison to linear generators.
Recently, Harald Niederreiter and Igor Shparlinski have made important advances in the theoretical study of nonlinear algorithms. The following papers are good starting points to learn about these developments,
Niederreiter, H. and Shparlinski, I.~E.: On the distribution and lattice structure of nonlinear congruential pseudorandom numbers. Finite Fields and Their Applications, 5: 246--253, 1999.

Niederreiter, H. and Shparlinski, I.~E.: On the distribution of pseudorandom numbers and vectors generated by inversive methods. Appl. Algebra Engrg. Comm. Comput., 10: 189--202, 2000.

Niederreiter, H. and Winterhof, A.: Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators. Finite Fields and Their Applications, 93: 387--399, 2000.

The following Master's Thesis written at pLab gives a graduate level introduction to inversive generators.
Weingartner, A.: Nonlinear congruential pseudorandom number generators. Master's thesis, University of Salzburg, 1994. Abstract available.

The comprehensive survey of Niederreiter
Niederreiter, H.: New developments in uniform pseudorandom number and vector generation. In Niederreiter, H. and Shiue, P.J.-S., editor(s), Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, volume 106 of Lecture Notes in Statistics. Springer-Verlag, Heidelberg New York, 1995.

covers not only inversive, but also other nonlinear methods to produce random numbers. This paper concentrates on theoretical results. It contains a wealth of references.

Eichenauer-Herrmann, his wife Eva Herrmann, and my former student Stefan Wegenkittl survey the present state of theoretical results for inversive and quadratic generators in

Eichenauer-Herrmann, J. and Herrmann, E. and Wegenkittl, S.: A survey of quadratic and inversive congruential pseudorandom numbers. In Proceedings of the Second International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Salzburg, July 9--12, 1996 of Lecture Notes in Statistics. Springer-Verlag, New York, 1997.

Many of these results remain state of the art.

 

CRYPTOGRAPHICAL GENERATORS
Good starting points for mathematicians are the survey paper of Lagarias

Lagarias, J.C.: Pseudorandom Numbers. Statistical Science, 8: 31--39, 1993.

and the classical paper on cryptographical random bit generators by Blum and Micali
Blum, M. and Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal of Computing, 13: 850--864, 1984.

Oded Goldreich's monograph might become a classic on pseudorandomness in cryptography, Michael Luby's book has become one already,
Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Springer Verlag, Berlin, 1999.

Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton Computer Science Notes, 1996.

Monte Carlo random number generation is different from cryptographical applications. Hugo Krawczyk has shown that all polynomial generators (like linear congruential generators, etc.) are predictable, see
Krawczyk, H.: How to predict congruential generators. In Brassard, G., editor(s), Advances in Cryptology-CRYPTO'89, volume 435 of Lecture Notes in Computer Science, pp. 138--153. Springer-Verlag, 1990.

The best-known statistical test in the context of cryptographical generators is Maurer's Universal Statistical Test
Maurer, U.: A Universal Statistical Test for Random Bit Generators. J. Cryptology, 5: 89--105, 1992.

see also Wegenkittl's extension
Wegenkittl, S.: Entropy Estimators and Serial Tests for Ergodic Chains. IEEE Transactions on Information Theory, 47: (6) 2480--2489, 2001.

Many other references and a concise discussion of practically all relevant concepts are contained in the fine book by Menezes, van Oorschot, and Vanstone, and in Bruce Schneier's monograph for practitioners in (mathematical) cryptography, Menezes, A.~J. and van Oorschot, P.~C. and Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton, 1997.

Schneier, B.: Applied Cryptography. Wiley, New York, Second edition, 1996.

 

back to the top

 

Research supported by FWF and Jubiläumsfond der OeNB

 
Advertisements

 

 

Home | Contact | Impressum | About us | Generators | Links | Literature | Software | Tests
Contact