How does the Mersenne's Twister work?
source link: https://www.cryptologie.net/article/331/how-does-the-mersennes-twister-work/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 gg. 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 ff: 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 gg again to output a random
number.
Mersenne Twister (MT) is like that, except:
- your first
state
is not used to output anyrandom
numbers - a
state
allows you to output not only one, but 624random
numbers (although this could be thought as one bigrandom
number) - the gg 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 ff function is called "twist", the gg function is called "temper". You can find out how each functions work by looking at the working code on the wikipedia page of MT.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK