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 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, mais échoue systématiquement sur deux des tests BigCrush de . 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. 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. C'est également un générateur de nombres pseudo-aléatoires de SPSS. 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. 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é.