An efficient lattice reduction method for F2-linear pseudorandom number generators using Mulders and Storjohann algorithm

Recent simulations often use highly parallel machines with many processors, and they need many pseudorandom number generators with distinct parameter sets, and hence we need an effective fast assessment of the generator with a given parameter set. Linear generators over the two-element field are good candidates, because of the powerful assessment via their dimensions of equidistribution. Some efficient algorithms to compute these dimensions use reduced bases of lattices associated with the generator. In this article, we use a fast lattice reduction algorithm by Mulders and Storjohann instead of Schmidt’s algorithm, and show that the order of computational complexity is lessened. Experiments show an improvement in the speed by a factor of three. We also report that just using a sparsest initial state (i.e., consisting of all 0 bits except one) significantly accelerates the lattice computation, in the case of Mersenne Twister generators.     

Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing

Simulated Annealing and Genetic Algorithms are important methods to solve discrete optimization problems and are often used to find approximate solutions for diverse NP-complete problems. They depend on randomness to change their current configuration and transition to a new state. In Simulated Annealing, the random choice influences the construction of the new state as well as the acceptance of that new state. In Genetic Algorithms, selection, mutation and crossover depend on random choices. We experimentally investigate the robustness of the two generic search heuristics when using pseudorandom numbers of limited quality. To this end, we conducted experiments with linear congruential generators of various period lengths, a Mersenne Twister with artificially reduced period lengths as well as quasi-random numbers as the source of randomness. Both heuristics were used to solve several instances of the Traveling Salesman Problem in order to compare optimization results. Our experiments show that both Simulated Annealing and the Genetic Algorithm produce inferior solutions when using random numbers with small period lengths or quasi-random numbers of inappropriate dimension. The influence on Simulated Annealing, however, is more severe than on Genetic Algorithms. Interestingly, we found that when using diverse quasi-random sequences, the Genetic Algorithm outperforms its own results using quantum random numbers.     

The gambler’s ruin problem with delays

A recent paper by  Pozdnyakov and Steele (2010) is devoted to the so-called binary-plus-passive design. Two problems that the authors do not consider can be identified with the classical gambler’s ruin problem in which delays are allowed.     

Pseudorandom number generators based on random covers for finite groups

Random covers for finite groups have been introduced in Magliveras et?al. (J Cryptol 15:285–297, 2002), Lempken et?al. (J Cryptol 22:62–74, 2009), and Svaba and van Trung (J Math Cryptol 4:271–315, 2010) for constructing public key cryptosystems. In this article we describe a new approach for constructing pseudorandom number generators using random covers for large finite groups. We focus, in particular, on the class of elementary abelian 2-groups and study the randomness of binary sequences generated from these generators. We successfully carry out an extensive test of the generators by using the NIST Statistical Test Suite and the Diehard battery of tests. Moreover, the article presents argumentation showing that the generators are suitable for cryptographic applications. Finally, we include performance data of the generators and propose a method of using them in practice.     

Asymptotic analysis of a risk process with high dividend barrier

In this paper we study a risk model with constant high dividend barrier. We apply Keilson’s (1966) results to the asymptotic distribution of the time until occurrence of a rare event in a regenerative process, and then results of the cycle maxima for random walk to obtain the asymptotic distribution of the time to ruin and the amount of dividends paid until ruin.     

Efficiency test of pseudorandom number generators using random walks

Markov chain Monte Carlo methods and computer simulations usually use long sequences of random numbers generated by deterministic rules, so-called pseudorandom number generators. Their efficiency depends on the convergence rate to the stationary distribution and the quality of random numbers used for simulations. Various methods have been employed to measure the convergence rate to the stationary distribution, but the effect of random numbers has not been much discussed. We present how to test the efficiency of pseudorandom number generators using random walks.     

Stochastic Optimization and the Gambler's Ruin Problem

Abstract

An analogy between stochastic optimization and the gambler's ruin problem is used to estimate the expected value of the number of function evaluations required to reach the extremum of a special objective function with a pafrticular random walk. The objective function is the sum of the squares of the independent variables. The optimization is accomplished when the random walk enters a suitably defined small neighborhood of the extremum. The results indicate that for this objective function the expected number of function evaluations increases as the number of dimensions to the five halves power. Results of extensive computations of optimizing random walks in spaces with dimensions ranging from 2 to 30 agree with the analytically predicted behavior.     

On the concentration of Sinai’s walk

We consider Sinai’s random walk in a random environment. We prove that for an interval of time [1,n]$[1,n]$ Sinai’s walk sojourns in a small neighborhood of the point of localization for the quasi-totality of this amount of time. Moreover the local time at the point of localization normalized by n$n$ converges in probability to a well defined random variable of the environment. From these results we get applications to the favorite sites of the walk and to the maximum of the local time.     

On the structure of digital explicit nonlinear and inversive pseudorandom number generators

We analyze the lattice structure and distribution of the digital explicit inversive pseudorandom number generator introduced by Niederreiter and Winterhof as well as of a general digital explicit nonlinear generator. In particular, we extend a lattice test designed for this class of pseudorandom number generators to parts of the period and arbitrary lags and prove that these generators pass this test up to very high dimensions. We also analyze the behavior of digital explicit inversive and nonlinear generators under another very strong lattice test which in its easiest form can be traced back to Marsaglia and provides a complexity measure essentially equivalent to linear complexity.     

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.     

常见随机数发生器的缺陷及组合随机数发生器的理论与实践

随机数是蒙特卡罗 Monte- Carlo方法的基础 .本文首先指出线性同余法和移位寄存器 (亦称 Tausworthe)序列等常见随机数发生器的一些缺陷 ;在此基础上介绍可产生具有优良品质随机数的组合发生器。本文既介绍理论结果 ,用以证明组合发生器确实可以优于单个发生器 ;也具体构造了几个可供实际使用的组合随机数发生器。严格而全面的统计检验表明 ,它们可以产生具有优良品质的随机数     

Higher-order Mond-Weir converse duality in multiobjective programming involving cones

In this work,we established a converse duality theorem for higher-order Mond-Weir type multiobjective programming involving cones.This flls some gap in recently work of Kim et al.[Kim D S,Kang H S,Lee Y J,et al.Higher order duality in multiobjective programming with cone constraints.Optimization,2010,59:29–43].     

On Marsaglia's lattice test for pseudorandom numbers

Nonlinear recursive congruential pseudorandom number generators with prime modulus and maximal period length are considered. Those generators are characterized which behave optimally with respect to Marsaglia's lattice test. An example for an extremely bad generator with this property is given, which demonstrates the weakness of this test.     

Security improvement on an anonymous key agreement protocol based on chaotic maps

In 2009, Tseng et al. proposed a password sharing and chaotic map based key agreement protocol (Tseng et al.’s protocol). They claimed that the protocol provided mutual authentication between a server and a user, and allowed the user to anonymously interact with the server to establish a shared session key. However, in 2011, Niu et al. have proved that Tseng et al.’s protocol cannot guarantee user anonymity and protocol security when there is an internal adversary who is a legitimate user. Also it cannot provide perfect forward secrecy. Then Niu et al. introduced a trust third party (TTP) into their protocol designing (Niu et al.’s protocol). But according to our research, Niu et al.’s protocol is found to have several unsatisfactory drawbacks. Based on reconsidering Tseng et al.’s protocol without introducing TTP, we give some improvements to meet the original security and performance requirements. Meanwhile our proposed protocol overcomes the security flaws of Tseng et al.’s protocol.     

On general best proximity pairs and equilibrium pairs in free abstract economies

In this paper, using Lassonde’s fixed point theorem for Kakutani factorizable multifunctions and Park’s fixed point theorem for acyclic factorizable multifunctions, we will prove new existence theorems for general best proximity pairs and equilibrium pairs for free abstract economies, which generalize the previous best proximity theorems and equilibrium existence theorems due to Srinivasan and Veeramani [P.S. Srinivasan, P. Veeramani, On best approximation pair theorems and fixed point theorems, Abstr. Appl. Anal. 2003 (1) (2003) 33–47; P.S. Srinivasan, P. Veeramani, On existence of equilibrium pair for constrained generalized games, Fixed Point Theory Appl. 2004 (1) (2004) 21–29], and Kim and Lee [W.K. Kim, K.H. Lee, Existence of best proximity pairs and equilibrium pairs, J. Math. Anal. Appl. 316 (2006) 433–446] in several aspects.     

一类随机游动上确界的密度的渐近性

Kluppelberg^[1], Asmussen 等^[2] 研究了增量有有限负均值的随机游动上确界的密度的渐近性. 该文则在 Denisov 等^[3], 程东亚和王岳宝^[4]的基础上, 进一步研究了增量均值为负无穷的随机游动上确界的密度的渐近性. 最后, 为了说明常见重尾分布大多满足上述结果的条件, 该文给出了一些分布族的性质.     

Asymptotic entropy of the ranges of random walks on discrete groups

Inspired by Benjamini et al.(2010) and Windisch(2010),we consider the entropy of the random walk ranges R_n formed by the first n steps of a random walk S on a discrete group.In this setting,we show the existence of h_R:=lim_(n→∞)H(R_n)/n called the asymptotic entropy of the ranges.A sample version of the above statement in the sense of Shannon(1948) is also proved.This answers a question raised by Windisch(2010).We also present a systematic characterization of the vanishing asymptotic entropy of the ranges.Particularly,we show that h_R=0 if and only if the random walk either is recurrent or escapes to negative infinity without left jump.By introducing the weighted digraphs Γ_n formed by the underlying random walk,we can characterize the recurrence property of S as the vanishing property of the quantity lim_(n→∞)H(Γ_n)/n,which is an analogue of h_R.     

Level crossing probabilities II: Polygonal recurrence of multidimensional random walks

In part I we proved for an arbitrary one-dimensional random walk with independent increments that the probability of crossing a level at a given time n is O(n−1/2). In higher dimensions we call a random walk ‘polygonally recurrent’ if there is a bounded set, hit by infinitely many of the straight lines between two consecutive sites a.s. The above estimate implies that three-dimensional random walks with independent components are polygonally transient. Similarly a directionally reinforced random walk on Z³ in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252] is transient. On the other hand, we construct an example of a transient but polygonally recurrent random walk with independent components on Z².     

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.