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.     

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.

     

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 Multidimensional 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 multidimensional 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. (Received 3 December 1998)     

Inversive congruential generator over a Galois ring of dimension <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">l</Emphasis></Superscript>

We consider the construction of of an inversive congruential generator over a Galois ring of odd dimension p ^l , whichwas proposed by Solé and Zinoviev for p = 2. Using the estimates of trigonometric sums on the sequences of pseudorandom numbers, we obtain the estimates of a discrepant function, a generated sequence of pseudorandom numbers, and the associated sequence of two-dimensional “overlapping” points.     

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.     

Construction of inversive congruential pseudorandom number generators with maximal period length

The inversive congruential method for generating uniform pseudorandom numbers is a particularly attractive alternative to linear congruential generators with their well-known inherent deficiencies like the unfavourable coarse lattice structure in higher dimensions. In the present paper the modulus in the inversive congruential method is chosen as a power of an arbitrary odd prime. The existence of inversive congruential generators with maximal period length is proved by a new constructive characterization of these generators.     

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)     

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.     

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.     

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.

     

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 a nonlinear congruential pseudorandom number generator

A nonlinear congruential pseudorandom number generator with modulus is proposed, which may be viewed to comprise both linear as well as inversive congruential generators. The condition for it to generate sequences of maximal period length is obtained. It is akin to the inversive one and bears a remarkable resemblance to the latter.

     

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 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 we obtain a stronger bound “on average” over all initial values. This bound is new even in the case when M = p is prime.     

一般组合逆同余法的算法与偏差分析

本文研究了逆同余产生伪随机数的方法，给出了一般的组合逆同余法算法．将已有结果进行理论比较，得到了一个较好的伪随机数序列的产生方法．     

Optimal coefficients modulo prime powers in the three-dimensional case

Summary For the three-dimensional case the existence of optimal coefficients, satisfying additional properties important in the theory of linear congruential pseudorandom numbers, is shown for prime power moduli.     

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.     

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.