# How does the Mersenne's Twister work? posted February 2016

Someone asked that question on reddit, and so I replied with a high level answer that should provide a clear enough view of the algorithm:

From a high level, here's what a PRNG is supposed to look like:

you start with a `seed`

(if you re-use the same `seed`

you will obtain the same `random`

numbers), you initialize it into a `state`

. Then, every time you want to obtain a `random`

number, you transform that `state`

with a one-way function \(g\). This is because you don't want people to find out the state out of the `random`

output.

You want another `random`

number? You first transform the `state`

with a one way function \(f\): this is because you don't want people who found out the `state`

to be able to retrieve past `states`

(forward secrecy). And then you use your function \(g\) again to output a `random`

number.

Mersenne Twister (MT) is like that, except:

- your first
`state`

is not used to output any`random`

numbers - a
`state`

allows you to output not only one, but 624`random`

numbers (although this could be thought as one big`random`

number) - the \(g\) function is reversible, it's not a one-way function, so MT it is not a cryptographically secure PRNG.

With more details, here's what MT looks like:

the \(f\) function is called "twist", the \(g\) function is called "temper". You can find out how each functions work by looking at the working code on the wikipedia page of MT.

## Comments

## mm

Very elegant explanation. :) Very helpful.

Thou I think it's 623 dimensions. [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf]

Thanks.

## test

test

## rd

Thanks for the explanation.

## Sam

Great article! Thanks

## Daz

Hi David.

Great explanation. I find these mathematical concepts and applications fascinating. Someone told me recently that one of our Lotto systems in Australia generates its numbers using a RNG. I would assume these systems would be water tight and that it would be impossible to crack them in a normal lifetime. Hence I guess they wouldn't use them, unless they use them with people thinking that is the case in the hope that no one would even contemplate trying lol. I'd be interested in your thoughts on this topic.

Thanks and best regards

Daz

([email protected])

## RenĂ©

Hi David,

By "one-way function", do you mean a non-injective map or is it a more subtle concept ? Maybe a map for which each number has at least a given (large) number of antecedents ?

RenĂ©

## david

It's non-injective, but it's more than that. One-way in cryptography usually refers to the pre-image resistance. See this explanation: https://freecontent.manning.com/hash-functions-and-security/

## W.J.R. Halyn

Interesting methodology, but I wrote (over 30 years ago) all my RNG coding to just get the program to "glance" at the present time and date in the computer, and extract one element of the date and several digits out of the Hours, Seconds and Hundredths of Seconds fields, blend them into a short creative string that was then converted back into numeric format, and continue with that number as the seed.... at EVERY instance of requiring a random number.

Hence, it was IMPOSSIBLE to re-start from the same seed number during any iteration of the program, so the resultant factors were ALWAYS truly random.

The seed itself was generated out of the random instant the call went out to create it. Literally, even rebooting the computer from scratch and running the program right away several times in a row would never start the same RNG process, because the "Pseudo"-random was no longer there; the "Random" was genuine. The fraction-of-a-second instant the call was initiated could never be duplicated... with a date and hour "grab" to further muddle any chance of repetition.

And a helluva lot simpler than doing that Twisting and Tempering, etc.!

## leave a comment...