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

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:236

Article

Harase, Shin

关键词: Random number generation;    Uniformity;    Lattice reduction algorithm;   

DOI  :  10.1016/j.cam.2011.06.005

来源: Elsevier

【 摘 要 】

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. (C) 2011 Elsevier B.V. All rights reserved.

【 授权许可】

Free