Mersenne Twister
Pour les articles homonymes, voir Mersenne (homonymie) et Twister.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Le Mersenne Twister est un générateur de nombres pseudo-aléatoires, réputé pour sa qualité, développé par Makoto Matsumoto et Takuji Nishimura en 1997.
L’algorithme est fondé 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 et présente les propriétés suivantes :
- sa période est de ;
- 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é, suivant les tests Diehard[1], mais échoue systématiquement sur deux des tests BigCrush de TestU01 (en).
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
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 nombres aléatoires par défaut en Python, Ruby, R, PHP, MATLAB et Stata depuis la version 2014. Il est également disponible en C++ depuis la version 2011 du standard[2].
C'est également un générateur de nombres pseudo-aléatoires de SPSS.
Avantages
La version la plus communément utilisée 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
Mersenne Twister, contrairement à l’algorithme Blum Blum Shub, est 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
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
- M. Matsumoto et T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. dans Modeling and Computer Simulations, 1998.
