めるせんぬついすたを理解した？

擬似乱数の生成でよく使われる方法は，過去の乱数のいくつかから次の乱数を作るという生成法．至って自然な考え方だけど，質の良い擬似乱数を作るには過去の乱数から次を作るところに沢山の工夫が必要になる．

n個前までの値を足し合わせて新しい値を作るだけだと，n次の原始多項式に対応した足し合わせをしても所詮 2^n-1 周期のM系列にしかならない．ワードサイズがいくつであろうが，ワード内の各ビットは独立にM系列なだけで，ワードサイズに依存せず 2^n-1 周期にしかならない（実際に乱数として出力する際にビットをごちゃ混ぜにする調律が行われるが，あくまで出力時に混ざるだけであって再帰部分では混ざらない）．これがいわゆるGFSRというやつ．

で，単純に足し合わせるのではなく，ビットの系列を再帰時にごちゃ混ぜにしてしまう（定式化上はワードに対して行列をかける操作）のがTwisted GFSRとかいうやつ．こいつはワードサイズを w とすると，w本のビット系列がくっついでしまっているので，全体としては nw 次の多項式で次のビットを計算していることになる．なので，この多項式が原始多項式であれば，2^nw-1周期とかいうむちゃくちゃなM系列になる．

が，適当に考えた混ぜ方が原始多項式に対応するかどうかの判定がむちゃくちゃ難しいところに問題がある．

で，それを早く判定できる方法を考えて，実際に良い混ぜ方を提案したのがメルセンヌツイスタ．ぶっちゃけメルセンヌツイスタの貢献ってのは，原始多項式の高速な判定法の提案と，それを上手く利用できる生成式のクラスを与えたことだと思う．MT19937作りましたじゃない．

だがしかし，原始多項式の高速な判定法は理解して（見て）いない…　これではメルセンヌツイスタを理解したことにはならないね．