Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> Two closely-related pseudo-random sequence generators are presented: The ${1 / P}$generator, with input P a prime, outputs the quotient digits obtained on dividing 1 by P. The $x^2 \bmod N$generator with inputs N, $x_0 $ (where $N = P \cdot Q$ is a product of distinct primes, each congruent to 3 mod 4, and $x_0 $ is a quadratic residue $\bmod N$), outputs $b_0 b_1 b_2 \cdots $ where $b_i = {\operatorname{parity}}(x_i )$ and $x_{i + 1} = x_i^2 \bmod N$.From short seeds each generator efficiently produces long well-distributed sequences. Moreover, both generators have computationally hard problems at their core. The first generator’s sequences, however, are completely predictable (from any small segment of $2|P| + 1$ consecutive digits one can infer the “seed,” P, and continue the sequence backwards and forwards), whereas the second, under a certain intractability assumption, is unpredictable in a precise sense. The second generator has additional interesting properties: from knowledge of $x_0 $ and N but n... <s> BIB001 </s> Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> Preface 1. Monte Carlo methods and Quasi-Monte Carlo methods 2. Quasi-Monte Carlo methods for numerical integration 3. Low-discrepancy point sets and sequences 4. Nets and (t,s)-sequences 5. Lattice rules for numerical integration 6. Quasi- Monte Carlo methods for optimization 7. Random numbers and pseudorandom numbers 8. Nonlinear congruential pseudorandom numbers 9. Shift-Register pseudorandom numbers 10. Pseudorandom vector generation Appendix A. Finite fields and linear recurring sequences Appendix B. Continued fractions Bibliography Index. <s> BIB002 </s> Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> The present invention relates to a fermentation process for producing allylic methyl-hydroxylated novobiocin and derivatives thereof. These hydroxy novobiocins (II) are useful as antibiotics. <s> BIB003 </s> Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> The Wolff algorithm is now accepted as the best cluster-flipping Monte Carlo algorithm for beating «critical slowing down.» We show how this method can yield incorrect answers due to subtle correlations in «high quality» random number generators <s> BIB004 </s> Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> Abstract The deficiencies of classical methods for uniform pseudorandom number generation have recently led to the development of alternative methods, such as nonlinear congruential methods. A particularly attractive nonlinear congruential method is the explicit inversive congruential method recently introduced by Eichenauer-Herrmann. We establish several new results on the structural and statistical properties of pseudorandom numbers generated by this method. These results demonstrate that this method is eminently suitable for the generation of parallel streams of pseudorandom numbers with desirable properties. <s> BIB005 </s> Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> Pseudorandom vectors are of importance for parallelized simulation methods. In this article we carry out a detailed analysis of the inversive method for the generation of uniform pseudorandom vectors. This method can be viewed as an analog of the inversive congruential method for pseudorandom number generation. We study, in particular, the periodicity properties and the behavior under the serial test for sequences of pseudorandom vectors generated by the inversive method. <s> BIB006 </s> Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> Summary Nonlinear congruential methods for generating uniform pseudorandom numbers show several attractive properties. The present paper gives a complete survey of recent work on this topic. <s> BIB007 </s> Uniform random number generators: a review <s> NONLINEAR GENERATORS <s> Stochastic simulation requires a reliable source of randomness. Inversive methods are an interesting and very promising new approach to produce uniform pseudorandom numbers. In this paper, we present evidence that these methods are an important contribution to our toolbox. We survey the outstanding performance of inversive pseudorandom number generators in theoretical and empirical tests, in comparison to linear generators. In addition, this paper contains tables of parameters to implement inversive congruential generators. <s> BIB008
Some argue that since the structure of linear sequences is too regular, nonlinear generators should be used instead BIB007 BIB008 Niederreiter 1995b; BIB002 . Nonlinearity can be introduced by either (a) using a linear transition function f with a nonlinear output function g, (b) using a nonlinear recurrence. A simple example of (a) is the ewlicit inuersiue generator of Eichenauer-Herrmann (1993) : let x, = an + c, for n > 0, where a # 0 and c are in H,, m prime, z,, = xi1 = (an + c)"+~ mod m, and %a = z,/m. The period is p = m and it can be shown BIB005 ) that every hyperplane in IRt contains at most t points from the set Tt. Other variants of inversive nonlinear generators can be found in BIB003 , EichenauerHerrmann (1995)) L'Ecuyer (1997c), BIB002 ) BIB006 ), Niederreiter (1995b , and the references given there. These nonlinear generators tend to avoid the planes and have the right asymptotic orders of magnitude for their discrepancies. Those based on power-of-two moduli, however, have defects similar to the LCGs and MRGs with power-of-two moduli (see, e.g., L'Ecuyer,  . Other nonlinear generators have also been proposed in the field of cryptology. For example, the BBS generator, proposed by BIB001 , evolves according to x, = ximl mod m, where m is the product of two distinct k-bit primes, both congruent to 3 modulo 4, and gcd(xa, m) = 1. At each step, the generator outputs the last v bits of Zn, where v is in o(log(k)). Under the assumption that factoring is hard, and that m and x0 are chosen "randomly" in a specific way, it is proven that no polynomial-time (in k) statistical test can distinguish (in some specific sense) the output of a BBS generator from a sequence of i.i.d. uniforms. This means that for large enough k, the generator should behave very nicely from a statistical point of view. But nobody knows for sure how large is large enough. For more about cryptographic-type generators, see   . Th ese g enerators are rather slow compared with those usually employed for simulation. where tl is the value taken by T, is too close to either 0 or 1. One can also construct a two-levels' test, by comparing the empirical distribution of (say) N "independent" copies of T to the theoretical distribution of T. When testing RNGs, an arbitrarily large sample size can be taken to increase the power of the test and come up with a clear decision when suspicious pvalues occur. One can reject 310 is p < lo-', for example, and increase the sample size or repeat the test with other segments of the sequence when p is suspicious (p = .005, for example). In most cases, clear evidence against Ho will quickly show up or suspicion will disappear. Note that when 310 is not rejected for a given test, this proves nothing. It may well be rejected by the next test. It may be a good idea to run important simulations twice using random number generators of totally different families (e.g., linear and nonlinear).  d escribes a set of tests considered as "standard" for testing RNG.s.  has proposed a battery of tests called DIEHARD, which he considers more stringent than the classical tests in  . A software package that contains most of the tests proposed so far, as well as several classes of generators implemented in generic form, is under development (L'Ecuyer 1996c). Examples of other statistical tests applied to random number generators can be found in BIB004 , L'Ecuyer (1992), L'Ecuyer (1994), L'Ecuyer, Cordeau, and Simard (1997), L'Ecuyer,  ) L'Ecuyer (1997f),  ,  . After extensive experiments with these tests, the following (among other things) has been observed: (i) All RNGs with period lengths less than 232 (say), especially the linear ones, fail several tests with relatively small sample sizes; (ii) RNGs with power-oftwo moduli are worst-behaved than those with prime moduli, especially for their low-order bits; (iii) LFSRs and GFSRs based on primitive trinomials, or lagged-Fibonacci and AWC/SWB generators, whose structure is too simplistic, also fail some tests spectacularly; (iv) Combined generators with long periods and good or fair structural properties (lattice structure or equidistribution) pass the tests quite well; (v) When a large fraction of the period is used, nonlinear inversive generators with prime modulus do better than the LCGs.