Uniform random numbers. Theory and practice. (English) Zbl 0841.65004

Tezuka, Shu

The Kluwer International Series in Engineering and Computer Science. 315. Dordrecht: Kluwer Academic Publishers. xii, 209 p. (1995).

Uniform random numbers, or more precisely uniform pseudorandom numbers, are a central tool in simulation methods. Not only are they needed when simulating a sequence of independent uniformly distributed random variables, they also form the basis of practically all standard algorithms for generating nonuniform random variates. This is one of the few books that concentrate on uniform pseudorandom number generation and do not discuss nonuniform random variates. It is a very useful feature of the book that related topics of great current interest, namely random sequences in cryptography and low-discrepancy sequences, are also treated.
After a brief introductory chapter which provides a general background on pseudorandom numbers, a summary of the required results from number theory is given in Chapter 2. The topics that are covered include modular arithmetic, polynomial arithmetic over finite fields, linear recurring sequences, lattice bases, and the theory of uniform distribution of sequences. Chapter 3 on linear congruential generators opens the main part of the book. The lattice structure and the spectral test for these generators are treated in a routine manner. An interesting section deals with the implementation of long-period linear congruential generators either by the AWC/SWB method of Marsaglia and Zaman or by using combined generators.
Chapter 4 contains a detailed discussion of shift-register generators. A unified treatment is presented in which these generators are viewed as linear congruential generators with respect to polynomial arithmetic over finite fields. In this way, classical generators such as Tausworthe generators and GFSR generators arise as special cases of a general scheme. The only nonlinear congruential generator discussed in the book is the inversive congruential method, and it is given a rather cursory treatment. A more complete account of nonlinear congruential generators can be found in a recent survey article of the reviewer [Monte Carlo and quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.-S. Shiue, eds.), Lect. Notes Stat. 106, 87-120 (1995)]. A summary of pertinent facts on cryptographically strong pseudorandom bit generators concludes Chapter 4. A brief survey of empirical statistical tests for uniform pseudorandom numbers is given in Chapter 5.
The final Chapter 6 is mainly devoted to low-discrepancy sequences. The central themes are \((t,k)\)-sequences and a special class of such sequences which the author calls generalized Niederreiter sequences. At the time of the writing of this book, these were considered to be among the best available low-discrepancy sequences. It is unfortunate that the significant improvements in the construction of \((t,k)\)-sequences that were recently obtained by the reviewer and Chaoping Xing [see e.g. Acta Arith. 73, 87-102 (1995)] could not be incorporated into the book. Thus, due to the rapid progress in the area, most of Chapter 6 is already outdated.
The book is written mainly for practitioners. Except for those parts based on the author’s own research, proofs are usually omitted, so that the book is not so suitable for students and researchers who try to gain a deeper understanding of the theory. But the user of pseudorandom numbers who wants to get a quick overview of the subject will find this book very helpful. There is also a bibliography of over 100 items for the reader who wants to follow up various matters more extensively.

Reviewer: H.Niederreiter (Wien)

MSC:

65C10	Random number generation in numerical analysis
11K45	Pseudo-random numbers; Monte Carlo methods
62-02	Research exposition (monographs, survey articles) pertaining to statistics
94A60	Cryptography

Keywords:

nonuniform random variates; uniform pseudorandom number generation; random sequences; cryptography; low-discrepancy sequences; modular arithmetic; polynomial arithmetic; linear recurring sequences; lattice bases; linear congruential generators; lattice structure; spectral test; Tausworthe generators; empirical statistical tests; \((t,k)\)-sequences; Niederreiter sequences; bibliography