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 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.

     

Extension of the notion of collision and avalanche effect to sequences of k symbols

In recent papers [14], [15] I studied collision and avalanche effect in families of finite pseudorandom binary sequences. Motivated by applications, Mauduit and Sárk?zy in [13] generalized and extended this theory from the binary case to k-ary sequences, i.e., to k symbols. They constructed a large family of k-ary sequences with strong pseudorandom properties. In this paper our goal is to extend the study of the pseudorandom properties mentioned above to k-ary sequences. The aim of this paper is twofold. First we will extend the definitions of collision and avalanche effect to k-ary sequences, and then we will study these related properties in a large family of pseudorandom k-ary sequences with ??small?? pseudorandom measures.     

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 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)     

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.     

Collision and avalanche effect in families of pseudorandom binary sequences

Recently a constructive theory of pseudorandomness of binary sequences has been developed and many constructions for binary sequences with strong pseudorandom properties have been given. In the applications one usually needs large families of binary sequences of this type. In this paper we adapt the notions of collision and avalanche effect to study these pseudorandom properties of families of binary sequences. We test two of the most important constructions for these pseudorandom properties, and it turns out that one of the two constructions is ideal from this point of view as well, while the other construction does not possess these pseudorandom properties. Communicated by Attila Pethő     

Construction of large families of pseudorandom binary sequences

In a series of papers Mauduit and Sárközy (partly with coauthors) studied finite pseudorandom binary sequences. They showed that the Legendre symbol forms a “good” pseudorandom sequence, and they also tested other sequences for pseudorandomness, however, no large family of “good” pseudorandom sequences has been found yet.In this paper, a large family of this type is constructed by extending the earlier Legendre symbol construction.     

On the pseudorandomness of binary and quaternary sequences linked by the gray mapping

Binary and quaternary sequences are the most important sequences in view of many practical applications. Any quaternary sequence can be decomposed into two binary sequences and any two binary sequences can be combined into a quaternary sequence using the Gray mapping. We analyze the relation between the measures of pseudorandomness for the two binary sequences and the measures for the corresponding quaternary sequences, which were both introduced by Mauduit and Sárközy. Our results show that each ‘pseudorandom’ quaternary sequence corresponds to two ‘pseudorandom’ binary sequences which are ‘uncorrelated’.     

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 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.     

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.

     

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.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

基于有限域中的二次特征生成的伪随机二进制格点

本文利用有限域的二次特征与乘法逆构造了大族的伪随机格点,并研究了其密码学性质:伪随机性、碰撞和雪崩效应.     

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.     

Concatenation of pseudorandom binary sequences

In the applications it may occur that our initial pseudorandom binary sequence turns out to be not long enough, thus we have to take the concatenation or merging of it with other pseudorandom binary sequences. Here our goal is study when we can form the concatenation of several pseudorandom binary sequences belonging to a given family? We introduce and study new measures which can be used for answering this question.     

大族长度为pq的伪随机k元序列

Mauduit与Sárkzy在一系列论文中研究了κ元序列的伪随机性.本文通过对模pq剩余类环Z_(pq)进行分割,进而结合离散对数的方法,构造了一大族长度为pq的伪随机κ元序列,并证明其具有很好的伪随机性.     

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.     

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 .