Mersenne Twister - Définition
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 219937 − 1 et présente les propriétés suivantes :
- sa période est de 219937 − 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.
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é.
