Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast lattice reduction for $ \mathbf{F}_2$-linear pseudorandom number generators

Authors: Shin Harase, Makoto Matsumoto and Mutsuo Saito
Journal: Math. Comp. 80 (2011), 395-407
MSC (2010): Primary 11K45; Secondary 65C10
Published electronically: June 18, 2010
MathSciNet review: 2728986
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Sequences generated by an $ {\bf 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 $ {\bf 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 [Enhancements On Off] (What's this?)

  • 1. R. Couture and P. L'Ecuyer, Lattice computations for random numbers, Math. Comput. 69 (2000), no. 230, 757-765. MR 1651748 (2000i:11125)
  • 2. R. Couture, P. L'Ecuyer, and S. Tezuka, On the distribution of $ k$-dimensional vectors for simple and combined tausworthe sequences, Math. Comput. 60 (1993), 749-761. MR 1176708 (93h:11085)
  • 3. M. Fushimi and S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Commun. ACM 26 (1983), no. 7, 516-523.
  • 4. S. Harase, Maximally equidistributed pseudorandom number generators via linear output transformations, Math. Comput. Simul. 79 (2009), no. 5, 1512-1519. MR 2488100 (2010a:65012)
  • 5. P. L'Ecuyer and R. Couture, An implementation of the lattice and spectral tests for multiple recursive linear random number generators, INFORMS Journal on Computing 9 (1997), no. 2, 206-217. MR 1477315
  • 6. P. L'Ecuyer and F. Panneton, $ {\bf 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.
  • 7. A. K. Lenstra, Factoring multivariate polynomials over finite fields, Journal of Computer and System Sciences 30 (1985), no. 2, 235 - 248. MR 801825 (87a:11124)
  • 8. K. Mahler, An analogue to Minkowski's geometry of numbers in a field of series, The Annals of Mathematics 42 (1941), no. 2, 488-522. MR 0004272 (2:350c)
  • 9. -, On a theorem in the geometry of numbers in a space of Laurent series, Journal of Number Theory 17 (1983), no. 3, 403-416. MR 724538 (85e:11043)
  • 10. J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory IT-15 (1969), 122-127. MR 0242556 (39:3887)
  • 11. 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.
  • 12. F. Panneton, P. L'Ecuyer, and M. Matsumoto, Improved long-period generators based on linear recurrences modulo $ 2$, ACM Trans. Math. Softw. 32 (2006), no. 1, 1-16. MR 2272349 (2007h:94033)
  • 13. S. Paulus, Lattice basis reduction in function fields., Algorithmic Number Theory. Lecture Notes in Computer Science (Berlin), vol. 1423, Springer-Verlag, 1998. MR 1726102 (2000i:11193)
  • 14. W. M. Schmidt, Construction and estimation of bases in function fields, J. Number Theory 39 (1991), no. 2, 181 - 224. MR 1129568 (93b:11079)
  • 15. S. Tezuka, The k-dimensional distribution of combined GFSR sequences, Math. Comput. 62 (1994), no. 206, 809-817. MR 1223233 (94i:65014)
  • 16. L. Wang and H. Niederreiter, Successive minima profile, lattice profile, and joint linear complexity profile of pseudorandom multisequences, J. Complex. 24 (2008), no. 2, 144-153. MR 2400313 (2009d:94063)
  • 17. L. Wang and Y. Zhu, $ F[x]$-lattice basis reduction algorithm and multisequence synthesis, Sci. in China Ser. F 44 (2001), 321-328. MR 1895107 (2003g:94031)
  • 18. L. Wang, Y. Zhu, and D.-Y. Pei, On the lattice basis reduction multisequence synthesis algorithm, IEEE Trans. Inform. Theory 50 (2004), no. 11, 2905-2910. MR 2097012

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K45, 65C10

Retrieve articles in all journals with MSC (2010): 11K45, 65C10

Additional Information

Shin Harase
Affiliation: Graduate School of Mathematical Sciences, The University of Tokyo, Tokyo, Japan

Makoto Matsumoto
Affiliation: Graduate School of Mathematical Sciences, The University of Tokyo, Tokyo, Japan

Mutsuo Saito
Affiliation: Department of Mathematics, Hiroshima University, Hiroshima, Japan

Received by editor(s): July 15, 2009
Received by editor(s) in revised form: October 18, 2009
Published electronically: June 18, 2010
Additional Notes: The first author was partially supported by Grant-in-Aid for JSPS Fellows 21$·$4427
The second author was partially supported by JSPS Grant-in-Aid for Challenging Exploratory Research 21654017, Scientific Research (A) 19204002 and JSPS Core-to-Core Program 18005.
The third author was partially supported by JSPS Grant-in-Aid for Challenging Exploratory Research 21654004
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society