Mersenne 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.
|
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 
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é, 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.
Sommaire |
Sécurité cryptographique [modifier]
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]
Les générateurs congruentiels linéaires (Linear Congruential Generator) ont une période é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]
- M. Matsumoto et T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. dans Modeling and Computer Simulations, 1998.
