The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto and Takuji Nishimura that is based on a matrix linear recurrence over a finite binary field. 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, 2^k-1]
The Mersenne twister is the default random number generator for Python, Ruby, R, PHP , MATLAB and also available in C++ since C++11.
The algorithm in its native form is not suitable for cryptography (unlike Blum Blum Shub). Observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations. 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.
Link
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, 2^k-1]
The Mersenne twister is the default random number generator for Python, Ruby, R, PHP , MATLAB and also available in C++ since C++11.
The algorithm in its native form is not suitable for cryptography (unlike Blum Blum Shub). Observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations. 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.
Link
In mathematics, a Mersenne number, named after Marin Mersenne (a French monk who began the study of these numbers in the early 17th century), is a positive integer that is one less than a power of two:
Mp=2p-1
Some definitions of Mersenne numbers require that the exponent p be prime, since the associated number must be composite if p is composite. These Mersenne numbers are also pernicious numbers.
A Mersenne prime is a Mersenne number that is prime. It is known that if 2p − 1 is prime then p is prime, so it makes no difference which Mersenne number definition is used. As of October 2009, 47 Mersenne primes are known. The largest known prime number (243,112,609 − 1) is a Mersenne prime. Since 1997, all newly-found Mersenne primes have been discovered by the “Great Internet Mersenne Prime Search” (GIMPS), a distributed computing project on the Internet.
Many fundamental questions about Mersenne primes remain unresolved. It is not even known whether the set of Mersenne primes is finite. The Lenstra–Pomerance–Wagstaff conjecture asserts that, on the contrary, there are infinitely many Mersenne primes and predicts their order of growth. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite, although this would follow from widely believed conjectures about prime numbers, for example, the infinitude of Sophie Germain primes congruent to 3 (mod 4).
A basic theorem about Mersenne numbers states that in order for Mp to be a Mersenne prime, the exponent p itself must be a prime number. This rules out primality for numbers such as M4 = 24 − 1 = 15: since the exponent 4 = 2×2 is composite, the theorem predicts that 15 is also composite; indeed, 15 = 3×5. The three smallest Mersenne primes are
M2 = 3, M3 = 7, M5 = 31.
Mp=2p-1
Some definitions of Mersenne numbers require that the exponent p be prime, since the associated number must be composite if p is composite. These Mersenne numbers are also pernicious numbers.
A Mersenne prime is a Mersenne number that is prime. It is known that if 2p − 1 is prime then p is prime, so it makes no difference which Mersenne number definition is used. As of October 2009, 47 Mersenne primes are known. The largest known prime number (243,112,609 − 1) is a Mersenne prime. Since 1997, all newly-found Mersenne primes have been discovered by the “Great Internet Mersenne Prime Search” (GIMPS), a distributed computing project on the Internet.
Many fundamental questions about Mersenne primes remain unresolved. It is not even known whether the set of Mersenne primes is finite. The Lenstra–Pomerance–Wagstaff conjecture asserts that, on the contrary, there are infinitely many Mersenne primes and predicts their order of growth. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite, although this would follow from widely believed conjectures about prime numbers, for example, the infinitude of Sophie Germain primes congruent to 3 (mod 4).
A basic theorem about Mersenne numbers states that in order for Mp to be a Mersenne prime, the exponent p itself must be a prime number. This rules out primality for numbers such as M4 = 24 − 1 = 15: since the exponent 4 = 2×2 is composite, the theorem predicts that 15 is also composite; indeed, 15 = 3×5. The three smallest Mersenne primes are
M2 = 3, M3 = 7, M5 = 31.