メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。1996年に国際会議で発表されたもので(1998年1月に論文掲載)松本眞と西村拓士
による。既存の疑似乱数列生成手法にある多くの欠点が無く、高品質の疑似乱数列を高速に生成できる。考案者らによる実装が修正BSDライセンスで公開されている。「メルセンヌ・ツイスタ」は厳密にはある手法に基づいた乱数列生成式(あるいは生成法)の族を指し、内部状態の大きさや周期は設定可能である。以下の長所と短所では、メルセンヌ・ツイスタ自体、よく使われている生成法のMT19937、さらにその実装について、区別することなく述べている。
長所
219937-1 という長い周期が証明されている。
この周期は、名前の由来にもなっているように メルセンヌ素数であり、保証されているいくつかの特徴はメルセンヌ素数を内部的に使用していることによって達成されている。実際上、これ以上の長い周期の擬似乱数を使用する理由はない。
高次元(623次元)に均等分布する(線形合同法#短所参照)。
このことは出力中の連続する値間の相関性が無視できる程度しかないということを意味する。例えば、32bit版のメルセンヌ・ツイスタを複数回呼び出して64bit、128bitなどの疑似乱数として利用しても統計的に安全である。
統計的に不適当な疑似乱数しか生成しない擬似乱数生成器を除けば、あらゆる擬似乱数生成法の中でもっとも速い(当時)。
近年、統計的な問題が少なく、メルセンヌ・ツイスタよりも高速な疑似乱数生成器がいくつか考案されている。疑似乱数の生成速度を優先する場合は、これらの生成器が役に立つ可能性がある。メルセンヌ・ツイスタの利点は、長周期性と均等性、および既に広範に使われテストされていることである(ただしCPUごとに最適化されたコードであれば、現時点でもメルセンヌ・ツイスタは十分に速い[要出典])。
出力の中のすべてのビットが統計的に十分ランダムである。
メルセンヌ・ツイスタの前身GFSRはそうではなかった。以下に詳述
メルセンヌ・ツイスタの手法を、以前の生成法に関連付けて表現すると一般・フィードバック・シフト・レジスタ(General Feedback Shift Register)をひねって(Twisted)調律した(Tempered)もの(略してTTGFSR)となる(実際に、元はそのように呼んでいた)。GFSRではワード中の各ビットは独立していたが、「ひねる」ことによって各ビットの周期が合わさって長い周期を実現できるようになっている。「調律」は生成された疑似乱数のワードのうち数ビットだけを取り出したときの高次元超立方体への均等分布を改良して理論値に近づけるための工夫である(メルセンヌ・ツイスタは「調律」がなくても623次元超立方体に均等分布する)。ここまでは先行するTT800と同様であるが、メルセンヌ・ツイスタでは、状態空間が長方形から1ビットだけ突き出した(あるいは31ビット欠けた)形をしている点に特徴がある。これは19937÷32が623余り1であることによる。このような状態空間をとることによって219937-1という周期を実現している。 多くのアプリケーションにとって、メルセンヌ・ツイスタは優れた疑似乱数生成法である。しかしながら、実際にプログラムで利用するにあたっては、いくつか留意すべき点がある。
短所
暗号論的擬似乱数生成器 (CSPRNG) ではない。
メルセンヌ・ツイスタは線形漸化式によって生成されるため、他の一般の疑似乱数生成法と同様に予測可能である。従って暗号用途で利用するには同様に、暗号学的ハッシュ関数のような非可逆な操作を通さなければならない。CryptMT
なお、上記の欠点のうち、内部ベクトルの大きさや零超過状態からの回復速度の問題は、SIMD-oriented Fast Mersenne Twister (SFMT) で改善されている。 一部のプログラミング言語では、デフォルトの疑似乱数生成器としてメルセンヌ・ツイスタが標準ライブラリに取り入れられている。
各種プログラミング言語におけるライブラリ