Fast lattice reduction for 𝐅₂-linear pseudorandom number generators

Harase, Shin; Matsumoto, Makoto; Saito, Mutsuo

doi:10.1090/S0025-5718-2010-02391-9

Fast lattice reduction for $\mathbf {F}_2$-linear pseudorandom number generators
HTML articles powered by AMS MathViewer

by Shin Harase, Makoto Matsumoto and Mutsuo Saito PDF

Math. Comp. 80 (2011), 395-407 Request permission

Abstract:

Sequences generated by an $\textbf {F}_2$-linear recursion have wide applications, in particular, pseudorandom number generation. The dimension of equidistribution with $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 $\textbf {F}_2[[t^{-1}]]$) associated to the output $\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.

References

Raymond Couture and Pierre L’Ecuyer, Lattice computations for random numbers, Math. Comp. 69 (2000), no. 230, 757–765. MR 1651748, DOI 10.1090/S0025-5718-99-01112-6
Raymond Couture, Pierre L’Ecuyer, and Shu Tezuka, On the distribution of $k$-dimensional vectors for simple and combined Tausworthe sequences, Math. Comp. 60 (1993), no. 202, 749–761, S11–S16. MR 1176708, DOI 10.1090/S0025-5718-1993-1176708-4
M. Fushimi and S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Commun. ACM 26 (1983), no. 7, 516–523.
Shin Harase, Maximally equidistributed pseudorandom number generators via linear output transformations, Math. Comput. Simulation 79 (2009), no. 5, 1512–1519. MR 2488100, DOI 10.1016/j.matcom.2008.06.006
Pierre L’Ecuyer and Raymond Couture, An implementation of the lattice and spectral tests for multiple recursive linear random number generators, INFORMS J. Comput. 9 (1997), no. 2, 206–217. MR 1477315, DOI 10.1287/ijoc.9.2.206
P. L’Ecuyer and F. Panneton, $\textbf {F}_2$-linear random number generators, Advancing the Frontiers of Simulation: A Festschrift in Honor of George Samuel Fishman (C. Alexopoulos, D. Goldsman, and J. R. Wilson, eds.), Springer-Verlag, 2009, pp. 169–193.
A. K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comput. System Sci. 30 (1985), no. 2, 235–248. MR 801825, DOI 10.1016/0022-0000(85)90016-9
Kurt Mahler, An analogue to Minkowski’s geometry of numbers in a field of series, Ann. of Math. (2) 42 (1941), 488–522. MR 4272, DOI 10.2307/1968914
Kurt Mahler, On a theorem in the geometry of numbers in a space of Laurent series, J. Number Theory 17 (1983), no. 3, 403–416. MR 724538, DOI 10.1016/0022-314X(83)90057-4
James L. Massey, Shift-register synthesis and $\textrm {BCH}$ decoding, IEEE Trans. Inform. Theory IT-15 (1969), 122–127. MR 242556, DOI 10.1109/tit.1969.1054260
M. Matsumoto and T. Nishimura, Mersenne twister: a $623$-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul. 8 (1998), no. 1, 3–30.
François Panneton, Pierre L’ecuyer, and Makoto Matsumoto, Improved long-period generators based on linear recurrences modulo 2, ACM Trans. Math. Software 32 (2006), no. 1, 1–16. MR 2272349, DOI 10.1145/1132973.1132974
Sachar Paulus, Lattice basis reduction in function fields, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 567–575. MR 1726102, DOI 10.1007/BFb0054893
Wolfgang M. Schmidt, Construction and estimation of bases in function fields, J. Number Theory 39 (1991), no. 2, 181–224. MR 1129568, DOI 10.1016/0022-314X(91)90044-C
Shu Tezuka, The $k$-dimensional distribution of combined GFSR sequences, Math. Comp. 62 (1994), no. 206, 809–817. MR 1223233, DOI 10.1090/S0025-5718-1994-1223233-9
Li-Ping Wang and Harald Niederreiter, Successive minima profile, lattice profile, and joint linear complexity profile of pseudorandom multisequences, J. Complexity 24 (2008), no. 2, 144–153. MR 2400313, DOI 10.1016/j.jco.2007.07.001
Liping Wang and Yuefei Zhu, $F[x]$-lattice basis reduction algorithm and multisequence synthesis, Sci. China Ser. F 44 (2001), no. 5, 321–328. MR 1895107
Li-Ping Wang, Yue-Fei Zhu, and Ding-Yi Pei, On the lattice basis reduction multisequence synthesis algorithm, IEEE Trans. Inform. Theory 50 (2004), no. 11, 2905–2910. MR 2097012, DOI 10.1109/TIT.2004.836670