Mersenne Twister

Un article de Wikipédia, l'encyclopédie libre.

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¹⁹⁹³⁷ − 1 et présente les propriétés suivantes :

• sa période est de 2¹⁹⁹³⁷ − 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.

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 1 Sécurité cryptographique 2 Voir aussi 3 Références 4 Liens externes

[modifier] Sécurité cryptographique

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é.

[modifier] Voir aussi

• Congruence sur les entiers

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.

[modifier] 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.

[modifier] Liens externes

• (en) Page officielle
• (en) Implémentation en C++
• (en) La GNU Scientific Library (GSL), contient une implémentation de Mersenne Twister

Générateurs de nombres pseudo-aléatoires Modifier

Rapides : Générateur congruentiel linéaire, Mersenne Twister, RANDU

Cryptographiques : Blum Blum Shub, Fortuna, ISAAC, Yarrow

Briques : Congruence sur les entiers, Fonction de hachage, Registre à décalage

Voir aussi le portail de la cryptologie

• Portail de l’informatique