Mersenne Twister

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 $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é, 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

Congruence sur les entiers

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

« Why MT? », sur hiroshima-u.ac.jp (consulté le 12 avril 2023).
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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.