Fast lattice reduction for 𝐅₂-linear pseudorandom number generators
Shin Harase, Makoto Matsumoto, Mutsuo Saito · Mathematics of Computation · 2010
Sequences generated by an F 2 \textbf {F}_2 -linear recursion have wide applications, in particular, pseudorandom number generation. The dimension of equidistribution with v v -bit accuracy is a most important criterion for the uniformity of the generated sequence. The fastest known method for computing these dimensions is proposed by Couture and L’Ecuyer, based on Lenstra’s lattice basis reduction and the dual lattice to the lattice of vector-valued generating functions (with components in the formal power series F 2 [ [ t − 1 ] ] \textbf {F}_2[[t^{-1}]] ) associated to the output F 2 \mathbf {F}_2 -vector sequence. In this paper we propose a similar but faster algorithm, where (1) the state space is used to represent vectors with components in the formal power series, (2) the dual lattice is not necessary, and (3) Lenstra reduction is replaced with a simpler basis reduction. The computational complexity of our method is smaller than for the Couture-L’Ecuyer method. Experiments show that our method improves the speed by a factor of 10 for Mersenne Twister MT19937 and for WELL generators with state sizes of 19937 bits and 44497 bits.