Mersenne Twister

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Développé par Makoto Matsumoto et Takuji Nishimura en 1997, le Mersenne Twister est un générateur de nombres pseudo-aléatoires particulièrement réputé pour sa qualité.

L’algorithme est basé sur un TGSFR (twisted generalised shift feedback register, un type particulier de registre à décalage à rétroaction) et tient son nom d’un nombre premier de Mersenne. Il existe au moins deux variantes majeures, la plus répandue étant MT 19937, utilisant le nombre premier de Mersenne 2^{19937}-1 et présente les propriétés suivantes :

  • sa période est de 2^{19937}-1 ;
  • il est uniformément distribué sur un grand nombre de dimensions (623 pour les nombres de 32 bits) ;
  • il est plus rapide que la plupart des autres générateurs (sauf les plus médiocres statistiquement) ;
  • il est aléatoire quel que soit le poids du bit considéré, et passe les tests Diehard[1].

Une révision de l'algorithme a été faite afin de combler quelques lacunes, notamment l'initialisation correcte, afin d'assurer la maximisation de la période.

Applications[modifier | modifier le code]

L'algorithme Mersenne Twister a été optimisé pour être utilisé dans le cadre de simulations de Monte-Carlo dans un grand nombre de domaines, migration de photons, coalescence du génome, biologie cellulaire et finance informatique. Le Mersenne Twister est le générateur de nombre aléatoires par défaut en Python, Ruby, R, PHP et MATLAB. Il est également disponible en C++ depuis la version 2011 du standard[2].

C'est également un générateur de nombre aléatoires de SPSS.

Avantages[modifier | modifier le code]

La version la plus communément utilisé de Mersenne Twister, MT19937, qui crée une suite d'entiers de 32-bits, possède une propriété intéressante : il possède une très longue période.

Sécurité cryptographique[modifier | modifier le code]

Mersenne Twister, contrairement à l’algorithme Blum Blum Shub, est cependant insuffisant pour une utilisation en cryptographie car des algorithmes tels que Berlekamp-Massey ou Reed-Sloane permettent d’en prédire le comportement. Il reste cependant très utilisé dans tous les domaines hors de la cryptographie en raison de son efficacité.

Voir aussi[modifier | modifier le code]

Les générateurs congruentiels linéaires (Linear Congruential Generator) ont une période inférieure ou égale à leur modulo. Hugo Foulon a écrit, en 1985, dans sa thèse nommée Les aléas du hasard qu'un générateur était de bonne qualité s'il respectait les règles de Knuth.

Références[modifier | modifier le code]

  1. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/reason.html
  2. ISO C++ - 26.5.3.2 Class template mersenne_twister_engine
  • M. Matsumoto et T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. dans Modeling and Computer Simulations, 1998.

Liens externes[modifier | modifier le code]