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.