1
$\begingroup$

Mersenne Twister generator has a period of (2^19937)-1, but it is period of internal states.

Any idea what is the effective period of MT 32 bit output - period over which 32 bit output does not repeat. It has to be smaller than (2^31)-1 but I couldn't find definite answer.

Thanks

$\endgroup$
3
$\begingroup$

The Mersenne Twister algorithm is not a cryptographically secure algorithm. The state can be revealed if enough output is available.

However, if the internal state will repeat after $2^{19937}-1$ then obviously this is also the period of the output, even if the output is just 32 bits.

With a period it's not about when a certain output repeats once, but if the output is repeated indefinitely - in other words, you get into a cycle. Because of this the output size doesn't really matter: the repetition is on all the output put together. You can have a large period even if the algorithm outputs single bits at a time.

Note that the internal state of the Mersenne twister is not 32 bits, it's a whopping 2.5KiB. So the state is (necessarily) large.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Right, however as I mentioned, I am looking for an answer to period over which 32 bit output does not repeat. Any leads. Thanks $\endgroup$ – mabel Jul 22 '17 at 8:38
  • $\begingroup$ There is no such thing: the output is indistinguishable from random by definition. If you don't want to have duplicates then you need an additional algorithm. Such as simply storing the previously generated numbers and comparing against that. $\endgroup$ – Maarten Bodewes Jul 22 '17 at 8:45
  • 2
    $\begingroup$ If your still having trouble understanding it, think about what happens if your looking at the last character of a hash chain. (repeated hashing of the same message) . The result of a hash depends on the entirety of what it is hashing. Therefore its periodicity is the periodicity of the hash chain it is in, despite you only looking at the last character. (It is possible that there is a smaller cyclic pattern present, but that is not guaranteed. If it did exist, it would have to be a divisor of the length of the total cycle). The same applies to your question about the Mersenne Twister. $\endgroup$ – Ninja_Coder Jul 23 '17 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.