Mersenne-Twister-- ist es eine Möglichkeit, einen bestimmten Zustand zu springen?

Question

Ich bin ein wenig unsicher über das richtige Forum für diese Frage. Es ist zwischen theoretischer comp. sci./math und Programmierung.

Ich verwende Mersenne-Twister Pseudo-Zufallszahlen zu erzeugen. Nun, von einem bestimmten Samen beginnen, würde Ich mag auf die n-te Zahl in der Folge springen.

Ich habe gesehen: http://www-personal.umich.edu/ ~ wagnerr / MersenneTwister.html , und ein Schema könnte wie folgt aussehen:

Nehmen wir an, ich brauche nur die erste Seite N Zahlen in der gesamten Zufallsfolge von bestimmten Samen s .
Ich spaltete die Sequenz in zu p Teilfolgen, Marsch durch alle N Zahlen, und speichern Sie die Zustandsvektor des Zufallszahlengenerator zu Beginn jeder Subsequenz.
Nun zu erreichen n -te Zahl, ich werde sehen, dass n fällt in der k -te Teilfolge und ich werde den Zustandsvektor laden für diese Subsequenz und erzeugt m aufeinander folgende Zufallszahl, wobei m-ten Reihe in der k-ten Teilsequenz die gleichen wie n-te Nummer in der vollständigen Sequenz ist (n = m + (k-1) * N / p).

Aber der Zustandsvektor ist 624 x 4 Bytes lang! Ich frage mich, ob es praktisch möglich ist, auf ein beliebiges Element in der Mersenne-Twister erzeugte Sequenz zu springen.

Answer 1

Yes it is possible! It's called Jump Ahead.

You can find all the details to do this with Mersenne Twister on the homepage of MT's authors. Code is available as well as scientific publications explaining the algorithm:

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

Answer 2

Today, there is a way to do this using discard. The complexity is linear in number of equivalent advances.

A working example:

  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

The Mersenne Twister can be represented as a (rather large) matrix over F₂ (the field containing the two elements 0 and 1). A transition to the next state is a multiplication by this matrix.

To jump to some arbitrary position in the stream you can compute the corresponding power of this matrix by repeated squaring, and multiply it with your initial state.

Answer 4

I think what you are asking for would be against the definition of a cryptographically secure random number generator, so unfortunately I don't think it's possible.