Mersenne twister

related topics
{math, number, function}
{rate, high, increase}
{system, computer, user}
{theory, work, human}
{food, make, wine}

The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞?) and Takuji Nishimura (西村 拓士?)[1] that is based on a matrix linear recurrence over a finite binary field F2. It provides for fast generation of very high-quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms.

Its name derives from the fact that period length is chosen to be a Mersenne prime. There are at least two common variants of the algorithm, differing only in the size of the Mersenne primes used. The newer and more commonly used one is the Mersenne Twister MT19937, with 32-bit word length. There is also a variant with 64-bit word length, MT19937-64, which generates a different sequence.

For a k-bit word length, the Mersenne Twister generates numbers with an almost uniform distribution in the range [0,2k − 1].

Contents

Application

The algorithm in its native form is not suitable for cryptography (unlike Blum Blum Shub). Observing a sufficient number of iterates (624 in the case of MT19937) allows one to predict all future iterates. A pair of cryptographic stream ciphers based on output from Mersenne twister has been proposed by Makoto Matsumoto et al. The authors claim speeds 1.5 to 2 times faster than Advanced Encryption Standard in counter mode.[2]

Full article ▸

related documents
Controllability
Euler's totient function
Symmetric group
Golomb coding
Kruskal's algorithm
Convex set
Search algorithm
Automated theorem proving
Constant of integration
Division algebra
Lebesgue measure
Exact sequence
Local ring
Probability space
Mersenne prime
Analytic geometry
Carmichael number
Separable space
Goodstein's theorem
Group representation
Well-order
Diophantine set
Kolmogorov space
Inverse limit
Banach fixed point theorem
Linear equation
Laurent series
Probability distribution
Cartesian product
Linear