Mersenne Twister-有没有办法跳至特定状态？

Question

我对这个问题的正确论坛有些不确定。它是在理论上之间的。 Sci./math和编程。

我使用Mersenne-Twister生成伪随机数。现在，从给定的种子开始，我想跳到序列中的n个数字。

我已经看到了： http://www-personal.umich.edu/~wagnerr/mersennetwister.html, ，一个方案可能如下：

假设，我只需要第一个 n 特定种子的完整随机序列中的数字 s.
我将序列分为 p 子序列，通过所有n个数字，并在每个子序列的开头保存随机数生成器的状态向量。
现在到达 n- 这个数字，我会看到 n 落在 k- 该子序列，我将加载该子序列的状态向量并生成 m 连续的随机数，其中k-th子序列中的m-then数与完整序列（n = m +（k-1） * n/p）中的n数字相同。

但是国家向量为624 x 4字节长！我想知道是否可以在Mersenne-Twister生成的序列中跳入任意元素。

Answer 1

对的，这是可能的！叫做 跳跃前进.

您可以在MT作者的主页上找到所有详细信息，可以与Mersenne Twister一起完成此操作。可以使用代码以及解释算法的科学出版物：

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/mt/jump/jump/index.html

Answer 2

今天，有一种方法可以使用 丢弃. 。复杂性在等效进步的数量上是线性的。

一个工作示例：

  std::mt19937 engine(0);
  std::uniform_int_distribution<int> dis(0, 9);
  auto generator = std::bind(std::ref(dis), std::ref(engine));

  qDebug() << "First sequence: ";
  for (int i = 0; i < 20; i++) {
    qDebug() << "Random value: " << generator();
  }

  engine.seed(0); // reset
  engine.discard(15); // discard the first 15 numbers from the first sequence
  qDebug() << "Last five numbers from first sequence: ";
  for (int i = 0; i < 5; i++) {
    qDebug() << "Random value: " << generator();
  }

Answer 3

Mersenne Twister可以表示为f上的（相当大）矩阵₂ （包含两个元素0和1的字段）。向下一个状态的过渡是该矩阵的乘法。

要跳到流中的某个任意位置，您可以通过重复平方来计算此矩阵的相应功率，并用您的初始状态将其乘以。

Answer 4

我认为您的要求是反对密码安全的随机数生成器的定义，因此不幸的是，我认为这是不可能的。