Suggestions of efficient self-similar generators

The growth of Grid computing and the Internet has been exponential in recent years. These high-speed communication networks have had a tremendous impact on our civilisation. High-speed communication networks offer a wide range of applications, such as multimedia and data intensive applications, which differ significantly in their traffic characteristics and performance requirements. Many analytical studies have shown that self-similar network traffic can have a detrimental impact on network performance, including amplified queueing delays and packet loss rates in broadband wide area networks. Thus, full understanding of the self-similar nature in teletraffic engineering is an important issue.This paper presents a detailed survey of self-similar generators proposed for generating sequential and fixed-length self-similar pseudo-random sequences for simulation in communication networks. We evaluate and compare the operational properties of the fixed-length and sequential generators of self-similar pseudo-random sequences. The statistical accuracy and time required to produce long sequences are discussed theoretically and studied experimentally. The evaluation of the generators concentrated on two aspects: (i) how accurately self-similar processes can be generated (assuming a given mean, variance and self-similarity parameter H), and (ii) how quickly the generators can generate long self-similar sequences. Overall, our results have revealed that the fastest and most accurate generators of the six sequential and five fixed-length sequence generators considered are the SRP-FGN, FFT and FGN-DW methods.     

Assessing the Quality of Pseudo-Random Number Generators

In this article, we describe a new yet simple statistical procedure to better assess the quality of pseudo-random number generators. The new procedure builds on the statistical test suite proposed by the National Institute of Standards and Technology (NIST) and is especially useful for applications in economics. Making use of properties of the binomial distribution, we estimate the conjoint significance level of the test. We apply the proposed procedure to several well-known pseudo-random number generators, and the results confirm its effectiveness.     

On a possible error of type II in statistical evaluation of pseudo-random number generators

In an earlier paper, cf. [7], the first author developed methods for evaluation of pseudo-random number generators based on ideas of computer simulation. More precisely, pseudo-random numbers of the tested generator are used to model certain distributions which can be compared with theoretical ones or with distributions modeled by means of well-known canonical generators. But this method can fail if essentially different generators produce simulations that cannot be distinguished by means of simple statistical tests developed in [7]. In the present paper two critical types of distributions, named geometric and arthmetic, are constructed that illustrate the circumstances above. Also it is shown how the subinterval method derived from the tests in [7] can serve to detect the described critical types of distributions. Additional aspects of old and new methods are shortly discussed.     

Very high performance pseudo-random number generation on DAP

Since the National DAP Service began at QMC in 1980, extensive use has been made of pseudo-random numbers in Monte Carlo simulation. Matrices of uniform numbers have been produced by various generators:

• 1.(a) multiplicative (x_{+ 1} = 13¹³x_n mod 2⁵⁹);
• 2.(b) very long period shift register (x⁴⁴²³ + x²⁷¹ + 1);
• 3.(c) multiple shorter period (x¹²⁷ + x⁷ + 1) shift registers generating several matrices per iteration.

The above uniform generators can also feed a normal distribution generator that uses the Box-Muller transformation.This paper describes briefly the generators, their implementation and speed. Generator (b) has been greatly speeded-up by re-implementation, and now produces more than 100 × 10⁶ high quality 16-bit numbers/s. Generator (c) is under development and will achieve even higher performance, mainly due to producing data in greater bulk. High quality numbers are expected, and performance will range from 400 to 800 × 10⁶ numbers/s, depending on how the generator is used.     

Simple extractors via constructions of cryptographic pseudo-random generators

Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) can be used for building extractors as well. Using this new technique we build extractors that do not use designs or polynomial-based error-correcting codes and that are very simple and efficient. For example, one extractor produces each output bit separately in O(log²n) time. These extractors work for weak sources with min-entropy λn, for arbitrary constant λ>0, have seed length O(log²n), and their output length is ≈n^λ/3.     

An efficient protocol for secure multicast key distribution in the presence of adaptive adversaries

In this paper, an efficient construction of multicast key distribution schemes based on semantically secure symmetric-key encryption schemes and cryptographically strong pseudo-random number generators is presented and analyzed. The proposed scheme is provably secure against adaptive adversaries leveraging the security amplification technique defined over the logical key hierarchy structures. Our protocol tolerates any coalition of revoked users; in particular, we do not assume any limit on the size or structure of the coalition. The proposed scheme is efficient as a performance of Join or Leave procedure requires 2 log(N) multicast activities defined over a sibling ancestor node set, 2 log(N) internal state updates of the underlying pseudo-random number generator and 2 log(N) symmetric-key encryption activities for N users in a session.     

扩展在上GF（3）新型自缩序列模型及研究

自收缩序列是一类重要的伪随机序列,而周期和线性复杂度是序列伪随机性的经典量度。如何构造自缩序列的新模型,使生成序列具有大的周期和高的线性复杂度是一个重要的问题。针对这一问题,构造了GF（3）上一种新型的自缩序列模型,利用有限域理论,研究了生成序列的周期和线性复杂度,得到一些主要结论：周期上界3ⁿ,下界3^2[n/3];线性复杂度上界3ⁿ,下界3^2[n/3]-1。进一步讨论了基于GF（3）上本原三项式和四项式的自缩序列的周期和线性复杂度。     

基于编织法的de Bruijn序列差异性研究

由于de Bruijn序列具有周期最大、元素分布均衡、线性复杂度较高等良好的伪随机性质,因此在序列密码的研究领域中占有重要位置,其中de Bruijn序列的构造问题一直是研究的热点问题之一.目前已有多种构造de Bruijn序列的方法,而对于构造所得de Bruijn序列的差异性则相对研究较少,本文主要讨论基于编织法得到的de Bruijn序列的差异性.基于编织法,高杨等人给出了一种由一条n级de Bruijn序列来构造四条2n级de Bruijn序列的方法.由于这四条2n级de Bruijn序列由两条编织序列I1和I2唯一决定,因此de Bruijn序列的差异性可由这两条编织序列的差异性来刻画,而这两条编织序列的差异性又可以转化为两个指定映射的差异性.映射的差异性问题进一步可归结为对n长状态(e0e2…e2n-2)来源序列的研究,最终本文得到两个映射出现差异的充要条件,进而得到这两个映射的差异数和差异率2(2^n-1+1)^-1.据此可知,由编织法构造的编织序列的差异率随着级数的增大而减少.     

A parallel Monte Carlo transport algorithm using a pseudo-random tree to guarantee reproducibility

We present a parallel Monte Carlo photon transport algorithm that insures the reproducibility of results. The important feature of this parallel implementation is the introduction of a pair of pseudo-random number generators. This pair of generators is structured in such a manner as to insure minimal correlation between the two sequences of pseudo-random numbers produced. We term this structure as a ‘pseudo-random tree’. Using this structure, we are able to reproduce results exactly in a asynchronous parallel processing environment. The algorithm tracks the history of photons as they interact with two carbon cylinders joined end to end. The algorithm was implemented on both a Denelcor HEP and a CRAY X-MP/48. We describe the algorithm and the pseudo-random tree structure and present speedup results of our implementation.     

An experimental evaluation of the importance of randomness in hill climbing searches applied to software engineering problems

Random number generators are a core component of heuristic search algorithms. They are used to build candidate solutions and reduce bias while transforming these solutions during the search. Despite their usefulness, random numbers also have drawbacks, as one cannot guarantee that all portions of the search space are covered by the search and must run an algorithm many times to statistically assess its behavior. Determine whether deterministic quasi-random sequences can be used as an alternative to pseudo-random numbers in feeding “randomness” into Hill Climbing searches addressing Software Engineering problems. We have designed and executed three experimental studies in which a Hill Climbing search was used to find solutions for two Software Engineering problems: software module clustering and requirement selection. The algorithm was executed using both pseudo-random numbers and three distinct quasi-random sequences (Faure, Halton, and Sobol). The software clustering problem was evaluated for 32 real-world instances and the requirement selection problem was addressed using 15 instances reused from previous research works. The experimental studies were chained to allow varying as few as possible experimental factors between any given study and its subsequent one. Results found by searches powered by distinct quasi-random sequences were compared to those produced by the pseudo-random search on a per instance basis. The comparison evaluated search efficiency (processing time required to run the search) and effectiveness (quality of results produced by the search). Contrary to previous findings observed in the context of other heuristic search algorithms, we found evidence that quasi-random sequences cannot outperform pseudo-random numbers regularly in Hill Climbing searches. Detailed statistical analysis is provided to support the evidence favoring pseudo-random numbers.     

Universal traversal sequences with backtracking

In this paper we introduce a new notion of traversal sequences that we call exploration sequences. Exploration sequences share many properties with the traversal sequences defined in Aleliunas et al. (Proceedings on the 20th Annual Symposium of Foundations of Computer Science, 1979, pp. 218–223), but they also exhibit some new properties. In particular, they have an ability to backtrack, and their random properties are robust under choice of the probability distribution on labels.Further, we present simple constructions of polynomial-length universal exploration sequences for some previously studied classes of graphs (e.g., 2-regular graphs, cliques, expanders), and we also present universal exploration sequences for trees. These constructions do not obey previously known lower bounds on the length of universal traversal sequences; thus, they highlight another difference between exploration and traversal sequences.     

Pseudorandom lattices for global optimization

Rationalization processes are proposed to improve uniformity in small samples for pseudorandom lattices in (0,1)ⁿ constructed from sequences produced by random number generators. On this basis, the space filtration and space contraction algorithms are developed for the solution of multimodal global optimization problems. Strong convergence to the global minimum value and convergence in measure onto the set of all global minimizers are proved. Numerical experiments are presented to illustrate a better uniformity provided by a rationalization process and the use of the space filtration algorithm for global optimization.     

A search for good pseudo-random number generators: Survey and empirical studies

This paper targets to search so-called good generators by doing a brief survey over the generators developed in the history of pseudo-random number generators (PRNGs), verify their claims and rank them based on strong empirical tests in same platforms. To do this, the genre of PRNGs developed so far are explored and classified into three groups — linear congruential generator based, linear feedback shift register based and cellular automata based. From each group, the well-known widely used generators which claimed themselves to be ‘good’ are chosen. Overall 30 PRNGs are selected in this way on which two types of empirical testing are done — blind statistical tests with Diehard battery of tests, battery rabbit of TestU01 library and NIST statistical test-suite as well as graphical tests (lattice test and space–time diagram test). Finally, the selected PRNGs are divided into 24 groups and are ranked according to their overall performance in all empirical tests.     

Pseudo-Randomness of Certain Sequences of <Emphasis Type="Italic">k</Emphasis> Symbols with Length <Emphasis Type="Italic">pq</Emphasis>

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sárközy and later extended to sequences of k symbols (or k-ary sequences). Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.     

综述:产生伪随机数的若干新方法

产生随机数是 Ｍｏｎｔｅ－Ｃａｒｌｏ方法的基础．本文简要综述有关方法,重点是近年来国际上热门的一些新方法与评论,包括作者们的一些工作．除了线性同余法外,还将涉及非线性同余法,Ｆｉｂｏｎａｃｃｉ,Ｔａｕｓｗｏｒｔｈｅ序列,进位加－借位减发生器法,以及乘子和增量也在递推中变化的复合素数发生器和基于混沌映射产生随机数的方法．除此之外,也介绍组合发生器,特别是介绍用于证明组合发生器优于单个发生器的一些理论结果,基于这些理论可实际地构造优良的随机数发生器．在本文中,我们也注意收集和指出某些发生器在应用中可…     

A pseudo-random sequence generation scheme based on RNS and permutation polynomials

Long period pseudo-random sequence plays an important role in modern information processing systems. Base on residue number system (RNS) and permutation polynomials over finite fields, a pseudorandom sequence generation scheme is proposed in this paper. It extends several short period random sequences to a long period pseudo-random sequence by using RNS. The short period random sequences are generated parallel by the iterations of permutation polynomials over finite fields. Due to the small dynamic range of each iterative calculation, the bit width in hardware implementation is reduced. As a result, we can use full look-up table (LUT) architecture to achieve high-speed sequence output. The methods to find proper permutation polynomials to generate long period sequences and the optimization algorithm of Chinese remainder theorem (CRT) mapping are also proposed in this paper. The period of generated pseudorandom sequence can exceed 2¹⁰⁰ easily based on common used field programmable gate array (FPGA) chips. Meanwhile, this scheme has extensive freedom in choosing permutation polynomials. For example, 10905 permutation polynomials meet the long period requirement over the finite field F _q with q ? 1(mod 3) and q ? 503. The hardware implementation architecture is simple and multiplier free. Using Xilinx XC7020 FPGA chip, we implement a sequence generator with the period over 2⁵⁰, which only costs 20 18kb-BRAMs (block RAM) and a small amount of logics. And the speed can reach 449.236 Mbps. The National Institute of Standards and Technology (NIST) test results show that the sequence has good random properties.     

Hyperbolic automorphisms of tori and pseudo-random sequences

A method for generating pseudo-random sequences of d-dimensional vectors is considered; it is based on theergodic theory of periodic orbits in the sense of [2] for unstable dynamical systems such as the hyperbolic automorphisms of the d-dimensional Torus. Since these systems enjoy strong chaotic properties, their orbits are both dense andchaotic in some sense, however the ergodic property holds only for orbits having initial points with irrational coordinates, the remaining ones being periodic. Unfortunately, those orbits are the only ones that a computer is able to generate. Since a pseudo-random sequence in [0,1] ^d is a long periodic orbit which has chaotic behaviour similar in some sense to the one of aperiodic orbits, in this note, we shall prove lower and upper bounds for the length of the period of orbits of the hyperbolic automorphisms of the d-dimensional Torus, expressed in terms of the (rational) starting point. The algorithms proposed are free of computational error, since they work in integer arithmetic. Surprisingly the elimination of the round off errors turns out in anincrease of the length of the period. Statistical testing and the problem of estimating the discrepancy of the obtained sequences are also treated.     

Empirical tests for statistical properties of some pseudorandom number generators

Statistical properties of software pseudorandom number generators are tested based on uniform distribution on a unit hypercube with dimensions from 1 to 15. Some CLHEP generators, the Mersenne Twister generator and the MCNP generator, are tested. Parts of the pseudorandom number sequences with poor statistical properties are found. Easy-to-rectify flaws of two CLHEP generators are detected.     

The microcomputer performance of uniform variate random number generators expressed in FORTRAN

The microcomputer performance of random number generators is an important component of uncertainty analysis in environmental modeling. The results of a performance study of 110 uniform variate pseudo-random number generators expressed in FORTRAN are presented. The algorithms tested include multiplicative, mixed, additive and quadratic congruential generators plus example combined and generalized feedback shift register generators. Results are presented for generator speed, period, and 17 statistical measures of number randomness quality. These results indicate that, based on both speed and number quality, the multiplicative linear congruential generator can yield superior performance. Specific moduli and multipliers are recommended for this generator. For relatively low period generators, explicit use of the integer modulus function provides superior performance. When high period generators are implemented, they should be based on the Schrage (1979) or Bongiovanni (1987) computational procedure for accomplishing the modulus operation with arithmetic that avoids explicit use of the modulus function.     

Infinitesimal Generators on the Quantum Group SUq(2) in the Classical and Anti-Classical Limit

In [5] we found an explicit formula for the infinitesimal generators of white noises on the quantum group SU _q (2) in the case q (-1, 1). In [7] we compared the case q (-1, 1) with the classical case q = 1 which corresponds to the infinitesimal generators of Lévy processes on SU(2). We pointed out that our formula is the perfect analogue of Hunt's formula which describes the classical infinitesimal generators. In the first part of these notes we find Hunt's formula for SU _q (2) in the anti-classical case q = -1. This completes our theory of infinitesimal generators on SU _q (2) for all q [-1, 1].In the second part of these notes we show that SU _q (2) is a 'good' quantization of SU(2). We show that not only states on the algebra of functions on SU(2), but even infinitesimal generators may be approximated in a suitable sense by states and infinitesimals generators on SU _q (2) for q (-1, 1). Simultaneously, we show that a similar result is true for SU _-1(2).