メルセンヌ・ツイスタ

概要

メルセンヌ・ツイスタ(MT, Primitive Twisted Generalized Feedback Shift Register Sequence)は非常によい性質を持ち合わせている擬似乱数生成アルゴリズムの一つで、様々なプログラミング言語の標準ライブラリに実装されている.メルセンヌ数を用いることで、この擬似乱数生成を実現しており、高次元においても均等分布する、長期的な周期、比較的高速、メモリ効率もよいといった特徴を持ちます.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • シードとなる値が必要
効果
  • 長期的な周期を持ち比較的高速かつメモリ効率もよく高次元でも均等分布する擬似乱数を得る
ポイント
  • ほとんど全ての統計的乱数テストをパス
  • 暗号論的擬似乱数生成にはなっていない
  • 多くのプログラミング言語の標準ライブラリに採用される
  • 入力の値に0が多い場合は、似たような数字が出てしまう
  • 上記0が多くなる問題はWELL等で改善

解 説

メルセンヌ・ツイスタ(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を行なって出力とする. が最後の工程です.
メルセンヌツイスタの計算
メルセンヌツイスタの概要
この章を学んで新たに学べる
Comments

Reasons
>>隠す