mersenne twiner - 有没有办法跳转到特定状态？

Question

我有点不确定这个问题的正确论坛。它是在理论比较之间。科学/数学和编程。

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

我看过这个： http://www-personal.umich.edu/~wagnerr/ MersenneTwister.html，一种方案如下：

假设，我只需要来自特定种子 s 的完整随机序列中的前 N 个数字。< br> 我将序列分成 p 个子序列，遍历所有 N 个数字，并将随机数生成器的状态向量保存在每个子序列的开头。
现在要达到第 n 个数字，我会看到 n 落在第 k 个子序列中，并且我将加载状态向量为此子序列并生成 m 个连续随机数，其中第 k 个子序列中的第 m 个数字与完整序列中的第 n 个数字相同 ( n = m + (k-1) * N /p）。

但状态向量的长度是 624 x 4 字节！我想知道实际上是否有可能跳转到 mersenne-twister 生成的序列中的任意元素。

Answer 1

是的，这是可能的！它被称为向前跳跃。

您可以在 MT 作者的主页上找到使用 Mersenne Twister 执行此操作的所有详细信息。提供代码以及解释该算法的科学出版物：

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

Answer 2

今天，有一种方法可以使用 discard 来做到这一点。复杂性与等效进展的数量呈线性关系。

一个工作示例：

  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

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