Compound nonlinear congruential pseudorandom numbers

The nonlinear congruential method for generating uniform pseudorandom numbers has several very promising properties. However, an implementation in multiprecision of these pseudorandom number generators is usually necessary. In the present paper a compound version of the nonlinear congruential method is introduced, which overcomes this disadvantage. It is shown that the generated sequences have very attractive statistical independence properties. The results that are established are essentially best possible and show that the generated pseudorandom numbers model true random numbers very closely. The method of proof relies heavily on a thorough analysis of exponential sums.     

Compound inversive congruential pseudorandom numbers: an average-case analysis

The present paper deals with the compound (or generalized) inversive congruential method for generating uniform pseudorandom numbers, which has been introduced recently. Equidistribution and statistical independence properties of the generated sequences over parts of the period are studied based on the discrepancy of certain point sets. The main result is an upper bound for the average value of these discrepancies. The method of proof is based on estimates for exponential sums.

     

Average equidistribution and statistical independence properties of digital inversive pseudorandom numbers over parts of the period

This article deals with the digital inversive method for generating uniform pseudorandom numbers. Equidistribution and statistical independence properties of the generated pseudorandom number sequences over parts of the period are studied based on the distribution of tuples of successive terms in the sequence. The main result is an upper bound for the average value of the star discrepancy of the corresponding point sets. Additionally, lower bounds for the star discrepancy are established. The method of proof relies on bounds for exponential sums.

     

Equidistribution properties of quadratic congruential pseudorandom numbers

This paper deals with the quadratic congruential method for generating uniform pseudorandom numbers. Equidistribution properties of the generated pseudorandom number sequences over parts of the period are considered based on the discrepancy of corresponding point sets. An upper bound for the average value of these discrepancies is established.     

On a new class of inversive pseudorandom numbers for parallelized simulation methods

Inversive methods are attractive alternatives to the linear method for pseudorandom number generation. A particularly attractive method is the digital explicit inversive method recently introduced by the authors. We establish some new results on the statistical properties of parallel streams of pseudorandom numbers generated by this method. In particular, we extend the results of the first author on the statistical properties of pseudorandom numbers generated by the explicit inversive congruential method introduced by Eichenauer-Herrmann. These results demonstrate that the new method is eminently suitable for the generation of parallel streams of pseudorandom numbers with desirable properties.     

On the Distribution of Compound Inversive Congruential Pseudorandom Numbers

 Inversive methods are interesting alternatives to linear methods for pseudorandom number generation. A particularly attractive method is the compound inversive congruential method introduced and analyzed by Huber and Eichenauer-Herrmann. We present the first nontrivial worst-case results on the distribution of sequences of compound inversive congruential pseudorandom numbers in parts of the period. The proofs are based on new bounds for certain exponential sums. (Received 2 March 2000; in revised form 22 November 2000)     

On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and quasi-Monte Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. We prove lower bounds on the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions which are much stronger than bounds known for general nonlinear congruential pseudorandom number generators.     

On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus

The inversive congruential method for generating uniform pseudorandom numbers has been introduced recently as an alternative to linear congruential generators with their coarse lattice structure. In the present paper the statistical independence properties of pairs of consecutive pseudorandom numbers obtained from an inversive congruential generator with prime power modulus are analysed by means of the serial test. Upper bounds for the discrepancy of these pairs are established which are essentially best possible. The results show that the inversive congruential method with prime power modulus performs uniformly satisfactorily under the serial test. The methods of proof rely heavily on the evaluation of certain exponential sums which resemble Kloosterman sums.     

Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus

This paper deals with the inversive congruential method with power of two modulusm for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that there exist parameters in the inversive congruential method such that the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude at leastm ^–1/3. The method of proof relies on a detailed analysis of certain rational exponential sums.     

Nonoverlapping pairs of explicit inversive congruential pseudorandom numbers

Recently, the explicit inversive congruential method with power of two modulus for generating uniform pseudorandom numbers was introduced. Statistical independence properties of the generated sequences have been studied by estimating the discrepancy of all overlapping pairs of successive pseudorandom numbers. In the present paper a similar analysis is performed for the subsets of nonoverlapping pairs. The method of proof relies on a detailed discussion of the properties of certain exponential sums.     

Exponential sums of nonlinear congruential pseudorandom number generators with Rédei functions

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. We give new bounds of exponential sums with sequences of iterations of Rédei functions over prime finite fields, which are much stronger than bounds known for general nonlinear congruential pseudorandom number generators.     

On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus,II

One of the alternatives to linear congruential pseudorandom number generators with their known deficiencies is the inversive congruential method with prime power modulus. Recently, it was proved that pairs of inversive congruential pseudorandom numbers have nice statistical independence properties. In the present paper it is shown that a similar result cannot be obtained fork-tuples withk≥3 since their discrepancy is too large. The method of proof relies on the evaluation of certain exponential sums. In view of the present result the inversive congruential method with prime power modulus seems to be not absolutely suitable for generating uniform pseudorandom numbers.     

Improved Upper Bounds for the Discrepancy of Pairs of Inversive Congruential Pseudorandom Numbers with Power of Two Modulus

This paper deals with the inversive congruential method with power of two modulus for generating uniform pseudorandom numbers in the interval [0, 1). Statistical independence properties of the generated sequences are studied based on the distribution of both overlapping and nonoverlapping pairs of successive pseudorandom numbers. Improved upper bounds for the discrepancy of these point sets in [0, 1)2 are established.     

Statistical independence of nonlinear congruential pseudorandom numbers

Statistical independence properties of recently proposed nonlinear congruential pseudorandom number generators are analyzed by means of the serial test. The results that are established are essentially best possible. The method relies heavily on bounds for exponential sums.     

On the Average Distribution of Inversive Pseudorandom Numbers

The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. The authors have recently introduced a new method for obtaining nontrivial upper bounds on the multidimensional discrepancy of inversive congruential pseudorandom numbers in parts of the period. This method has also been used to study the multidimensional distribution of several other similar families of pseudorandom numbers. Here we apply this method to show that, “on average” over all initial values, much stronger results than those known for “individual” sequences can be obtained.     

On the Linear Complexity Profile of Nonlinear Congruential Pseudorandom Number Generators with Dickson Polynomials

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected. Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.     

Pseudorandom vector generation by the compound inversive method

Pseudorandom vectors are of importance for parallelized simulation methods. In this paper a detailed analysis of the compound inversive method for the generation of -dimensional uniform pseudorandom vectors, a vector analog of the compound inversive method for pseudorandom number generation, is carried out. In particular, periodicity properties and statistical independence properties of the generated sequences are studied based on the discrete discrepancy of -tuples of successive terms in the sequence. The results show that the generated sequences have attractive statistical independence properties for pseudorandom vectors of dimensions .

     

Inversive congruential pseudorandom numbers: distribution of triples

This paper deals with the inversive congruential method with power of two modulus for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that, on the average over the parameters in the inversive congruential method, the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude between and . The method of proof relies on a detailed discussion of the properties of certain exponential sums.

     

Distribution of Nonlinear Congruential Pseudorandom Numbers Modulo Almost Squarefree Integers

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present a new bound on the s-dimensional discrepancy of nonlinear congruential pseudorandom numbers over the residue ring \Bbb Z_M{\Bbb Z}_M modulo M for an “almost squarefree” integer M. It is useful to recall that almost all integers are of this type. Moreover, if the generator is associated with a permutation polynomial over \Bbb Z_M{\Bbb Z}_M we obtain a stronger bound “on average” over all initial values. This bound is new even in the case when M = p is prime.     

On the distribution of inversive congruential pseudorandom numbers in parts of the period

The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present the first nontrivial bounds on the discrepancy of individual sequences of inversive congruential pseudorandom numbers in parts of the period. The proof is based on a new bound for certain incomplete exponential sums.