概要
Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに になる。
Xorshift
説明は Wikipedia に丸投げする。
本記事では簡略化のため、実装例の一番上にある周期 の実装について議論する。
Zobrist hashing
個の要素があるとして、要素
に乱数
を割り当てる。
このとき、集合
の hash
を
で定める。
ただし
は bitwise xor とする。
この hashing の方法を Zobrist hashing と呼ぶ。
hash の衝突
異なる集合 について
となることを衝突と呼ぶ。
Zobrist hashing の場合
であるから、
かつ
となるような
が分かれば衝突を引き起こすことができる。
結論から言うと、 を Xorshift が
番目に出力した値として設定した場合、seed に依存せず
となるような
が存在する。
Xorshift の乱数列は途中から切り出しても何らかの seed を与えた Xorshift の乱数列であるから、
の設定が行われるまでに何度か乱数生成されていても衝突することになる。
思いつく回避方法を挙げる
の設定を行う際に
1 つ飛ばしや逆順にするなどの*1 変化を加える。ソースコードを読まれた場合対応される可能性がある。- Xorshift における shift の幅などを変える。ソースコードを読まれると対応される上、パラメータを間違えると乱数の質が落ちる。
- Xorshift 以外の乱数生成アルゴリズムを用いる。
の存在の証明、及び構成方法
32 bit 整数をベクトル空間 の元として解釈する。
整数の xor が
における
に対応することに注意せよ。
このとき、Xorshift における演算は全て
上の線形変換となっている。
従って、線形写像
によって Xorshift は以下のように表現できる (酷く厳密性に欠ける表現ではあるが)。
V Xorshift() { static V y = seed; y = A(y); return y; }
つまり、Xorshift の乱数列は初項を として
と表現される。
の最小多項式を
とすると、定義より
である。
とすると、
は求める集合になっている。
Cayley-Hamilton の定理より、 として最小多項式ではなく固有多項式を用いても良い。
周期
の実装例を用いた場合でも、全く同様の議論で衝突を起こすことができる。
Wikipedia の 32 bit の実装を衝突させる例
固有多項式を用いて、 を得た。
seed を自由に変えて実行してみると、毎回 hash が衝突していることが分かる。
追記
における
乗は
の指数を
倍したものに等しいため、Xorshift を
つ飛ばしにしてもそのまま衝突する。
また、
は reverse について不変なので、Xorshift を逆から読んでも衝突する。
*1:この変化は役に立たない。追記を参照せよ。