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.     

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ő     

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.     

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.     

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.     

研究伪随机数序列独立性的均匀偏度法

§1 引言 由具有在[0,1]上均匀分布的总体中产生的简单子样称为随机数序列,其中的每一样本称为随机数。所谓伪随机数序列,一般是指用数学递推公式所产生的随机数序列。如最常见的乘同余方法,它所产生的伪随机数序列就是对给定的正整数M和小于M的任意正整数初值β_1,用如下递推公式确定的:     

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.     

Recent trends in random number and random vector generation

A survey of recent work in the areas of uniform pseudorandom number and uniform pseudorandom vector generation is presented. The emphasis is on methods for which a detailed theory is available. A progress report on the construction of quasirandom points for efficient multidimensional numerical integration is also given.     

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.     

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 multidimensional distribution of the subset sum generator of pseudorandom numbers

We show that for a random choice of the parameters, the subset sum pseudorandom number generator produces a sequence of uniformly and independently distributed pseudorandom numbers. The result can be useful for both cryptographic and quasi-Monte Carlo applications and relies on bounds of exponential sums.

     

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.     

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.     

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.     

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

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

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.     

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.     

Pseudorandom sequences constructed by the power generator

Summary We study the pseudorandom properties of the power generator (which includes as special cases the RSA generator and the Blum--Blum--Shub generator). In order to estimate the pseudorandom measures character sums with exponential functions are used.     

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)