xorshift

概要

xorshiftは、近年発表されたビット演算のみで非常に高速に長期的な周期の乱数を得ることができる擬似乱数生成アルゴリズムです.しかし乱数を評価する統計的なテストに幾らか落ちており、xorshiftは乱数として信用できないとする声もあります.複数の発展系がありGoogleChromeでも発展系のxorshift+が使用されます.乱数は暗号学的安全性は保証されません.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • シードとなる値が必要.それを元に次の乱数を生成.
効果
  • ビット演算のみの操作で、非常に高速に乱数を生成
  • 擬似乱数を生成
ポイント
  • 周期はbit数nを用いて2^n-1となる
  • 決定論的挙動であるため暗号学的安全性はない
  • 改良のないxorshiftは統計テストに落ちいているが、その改善は容易

解 説

xorshiftは、近年発表されたビット演算のみで非常に高速に長期的な周期の乱数を得ることができる擬似乱数生成アルゴリズムです. しかし乱数を評価する統計的なテストに幾らか落ちており、xorshiftは乱数として信用できないとする声もあります. 複数の発展系がありGoogleChromeでも発展系のxorshift+が使用されます.乱数は暗号学的安全性は保証されません. 発展系は非線形処理などを加えるなどして弱点の克服をしている.
xorshiftとは
C++
1
2
3
4
5
6
int xorshift(x){
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}
xorshift(32bit)版のコード.
xorshiftは、32bit版において\(2^{32}-1\)の長さの周期になります.128bit版では\(2^{128}-1\)の長さの周期になります. 128bit版の生成器では、Diehard Testをパスし、BigCrushのテストに落ちています.
xorshiftの特性
この章を学んで新たに学べる
Comments

Reasons
>>隠す