期刊
MATHEMATICS AND COMPUTERS IN SIMULATION
卷 100, 期 -, 页码 103-113出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.matcom.2014.02.002
关键词
Random number generation; Lattice structure; Statistical test
类别
资金
- MEXT, Japan [24.7985, 21654017, 23244002]
- Grants-in-Aid for Scientific Research [23244002, 12J07985, 21654017] Funding Source: KAKEN
Sequence generators obtained by linear recursions over the two-element field F-2, i.e., F-2-linear generators, are widely used as pseudorandom number generators. For example, the Mersenne Twister MT19937 is one of the most successful applications. An advantage of such generators is that we can assess them quickly by using theoretical criteria, such as the dimension of equidistribution with nu-bit accuracy. To compute these dimensions, several polynomial-time lattice reduction algorithms have been proposed in the case of F2-linear generators. In this paper, in order to assess non-random bit patterns in dimensions that are higher than the dimension of equidistribution with v-bit accuracy, we focus on the relationship between points in the Couture L'Ecuyer dual lattices and F-2-linear relations on the most significant v bits of output sequences, and consider a new figure of merit N-nu, based on the minimum weight of F-2-linear relations whose degrees are minimal for v. Next, we numerically show that MTI9937 has low-weight F-2-linear relations in dimensions higher than 623, and show that some output vectors with specific lags are rejected or have small p-values in birthday spacings tests. We also report that some variants of Mersenne Twister, such as WELL generators, are significantly improved from the perspective of N-nu. (C) 2014 IMACS. Published by Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据