An efficient lattice reduction method for F2-linear pseudorandom number generators using Mulders and Storjohann algorithm
An efficient lattice reduction method for F2-linear pseudorandom number generators using Mulders and Storjohann algorithm
复制标题
DOI：
10.1016/j.cam.2011.06.005
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
S. Harase
中科院分区：
文献类型：
--
作者：
S. Harase
最近的模拟经常使用高度并行的机器与许多处理器，他们需要许多不同的参数集的伪随机数发生器，因此，我们需要一个有效的快速评估与给定的参数集的发生器。二元域上的线性生成元是很好的候选者，因为通过它们的等分布维数可以进行强大的评估。计算这些维度的一些有效算法使用与生成器相关联的格的缩减基。本文用Mulders和Storjohann提出的快速格点约简算法代替了施密特的格点约简算法，并证明了该算法的计算复杂度大大降低。实验表明，速度提高了三倍。我们还报告说，只需使用最稀疏的初始状态（即，由除一位之外的所有0位组成）在梅森扭曲发生器的情况下显著加速了晶格计算。
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.