メルセンヌ・ツイスタ

メルセンヌ・ツイスタ(MT, Primitive Twisted Generalized Feedback Shift Register Sequence)は非常によい性質を持ち合わせている擬似乱数生成アルゴリズムの一つで、様々なプログラミング言語の標準ライブラリに実装されている. メルセンヌ数を用いることで、この擬似乱数生成を実現しており、高次元においても均等分布する、長期的な周期、比較的高速、メモリ効率もよいといった特徴を持ちます.

発案者らのメルセンヌ・ツイスタに関するプロジェクトページです.

メルセンヌ・ツイスタは、\(2^{19937} -1\)といった長期的な周期を持ちます. 値は予測可能なものであるため暗号論的安全性はありません. また、欠点として、入力に0が多い列だとしばらくは0が多いままになってしまいます. 幾らかのそれからの回復方法としてWELLなどが提案されています.

メルセンヌツイスタの計算は複雑ではありません. 以下の漸化式を計算するのが大雑把に行なっていることです. 以下の式における\(n,m,w,r,A\)は全て定数であらかじめ決めてから使用します.定数でないのは、次の値を求めるときにインクリメントする\(k\)と\(x_k\)です. $$x_{k+n} = x_{k+m}\oplus ((x_k^{uppper\ r\ bit }|| x_{k+1}^{lower\ w-r\ bit })A)$$ 少し複雑に見えますが、要は、 1. \(x_k\)の上位r bitと\(x_{k+1}\)の下位w-r bitをくっつける. 2. 1.の結果にAをかける 3. それを\(x_{k+m}\)とXOR(\(\oplus\))を取る 実は上記の式には表記されていない工夫として、Tempering Transform(焼き戻し変換)を3.の後に行うというのがあります.これは統計的に偏ってしまう出力を再度均一にする効果を持ちます. なので、 4. Tempering Transformを行なって出力とする. が最後の工程です.