An efficient lattice reduction method for \(\mathbf F_2\)-linear pseudorandom number generators using Mulders and Storjohann algorithm (Q645697)

The author of this article studies the efficiency of algorithms for assessing the quality of certain pseudorandom number generators. In particular, the paper deals with the question of how to efficiently calculate the dimension of equidistribution of pseudorandom number generators based on linear recurrences over the finite field \(\mathbb{F}_2\). The dimension of equidistribution can be calculated by methods of linear algebra, and several researchers have proposed ways of speeding up the calculation, using lattice reduction algorithms. Here, the author proposes a further improvement, namely by employing a lattice reduction algorithm due to \textit{T. Mulders} and \textit{A. Storjohann} [J. Symb. Comput. 35, No.~4, 377--401 (2003; Zbl 1028.65038)], which lowers the complexity of computing the dimension of equidistribution. Numerical experiments show a speed-up by a factor of three. Furthermore, the author reports that using sparsest initial states considerably reduces the computing time for Mersenne Twister generators.