Mersenne Twister

Post Reply
User avatar
Pigeon
Posts: 18055
Joined: Thu Mar 31, 2011 3:00 pm

Mersenne Twister

Post by Pigeon » Tue Oct 09, 2012 5:47 am

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

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.


User avatar
Pigeon
Posts: 18055
Joined: Thu Mar 31, 2011 3:00 pm

Re: Mersenne Twister

Post by Pigeon » Tue Oct 09, 2012 10:58 pm

Pernicious number

In number theory, a pernicious number is a positive integer that has a prime number of 1s in its binary representation. Equivalently, the sum of the digits of a pernicious number, when represented in base 2, is a prime.

The first pernicious number is 3, since 3 = 11 (base 2) and 1 + 1 = 2, which is a prime. The next pernicious number is 5, since 5 = 101 (base 2), followed by 6, 7 and 9.

Properties

- No power of two is a pernicious number. This is trivially true, because powers of two in binary form are represented as a one followed by zeros. Similarly every number of the form 2n + 1 is a pernicious number.

- Every even perfect number is a pernicious number. This is based on the fact that every even perfect number can be represented as 2p−1(2p − 1) with p a prime. Owing to this form, every even perfect number is represented in binary as p ones followed by p − 1 zeros.

- A number of the form 2p − 1 with prime p is a pernicious number known as a Mersenne number.

Related numbers

Odious numbers are numbers with an odd number of 1s in their binary expansion.

Evil numbers are numbers with an even number of 1s in their binary expansion.


User avatar
Royal
Posts: 10562
Joined: Mon Apr 11, 2011 5:55 pm

Re: Mersenne Twister

Post by Royal » Wed Oct 10, 2012 4:40 am

Keep going.

User avatar
Pigeon
Posts: 18055
Joined: Thu Mar 31, 2011 3:00 pm

Re: Mersenne Twister

Post by Pigeon » Wed Oct 10, 2012 6:04 pm

On-Line Encyclopedia of Integer Sequences
OEIS

The On-Line Encyclopedia of Integer Sequences (OEIS), also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs. In October 2009, the intellectual property and hosting of the OEIS were transferred to the OEIS Foundation. OEIS records information on integer sequences of interest to both professional mathematicians and amateurs, and is widely cited. As of 20 November 2011 it contains over 200,000 sequences, making it the largest database of its kind

Neil Sloane started collecting integer sequences as a graduate student in 1965 to support his work in combinatorics. The database was at first stored on punch cards. He published selections from the database in book form twice:

A Handbook of Integer Sequences (1973, ISBN 0-12-648550-X), containing 2,372 sequences in lexicographic order and assigned numbers from 1 to 2372.

The Encyclopedia of Integer Sequences with Simon Plouffe (1995, ISBN 0-12-558630-2), containing 5,488 sequences and assigned M-numbers from M0000 to M5487. The Encyclopedia includes the references to the corresponding sequences (which may differ in their few initial terms) in A Handbook of Integer Sequences as N-numbers from N0001 to N2372 (instead of 1 to 2372.) The Encyclopedia includes the A-numbers that are used in the OEIS, whereas the Handbook did not.

These books were well received and, especially after the second publication, mathematicians supplied Sloane with a steady flow of new sequences. The collection became unmanageable in book form, and when the database had reached 16,000 entries Sloane decided to go online—first as an e-mail service (August 1994), and soon after as a web site (1996). As a spin-off from the database work, Sloane founded the Journal of Integer Sequences in 1998. The database continues to grow at a rate of some 10,000 entries a year. Sloane has personally managed 'his' sequences for almost 40 years, but starting in 2002, a board of associate editors and volunteers has helped maintain the database.

Link


Post Reply