Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
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
  • Email: sharase@orange.ocn.ne.jp
  • Makoto Matsumoto
  • Affiliation: Graduate School of Mathematical Sciences, The University of Tokyo, Tokyo, Japan
  • Email: matumoto@ms.u-tokyo.ac.jp
  • Mutsuo Saito
  • Affiliation: Department of Mathematics, Hiroshima University, Hiroshima, Japan
  • Email: saito@math.sci.hiroshima-u.ac.jp
  • 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$\cdot$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
  • © Copyright 2010 American Mathematical Society
  • Journal: Math. Comp. 80 (2011), 395-407
  • MSC (2010): Primary 11K45; Secondary 65C10
  • DOI: https://doi.org/10.1090/S0025-5718-2010-02391-9
  • MathSciNet review: 2728986