TinyMTの逆関数

tl;dr

• おおむねはおだんさんの記事の通り。
• この記事で付け加えたいのは以下の2点
  • $A^{-1}$と
    $B^{-1}$を行列を使わずに書くどうなるか
  • 上記の考察には不十分な点があり、逆関数になっていない

$A^{-1}$と

$B^{-1}$をビット演算だけで行う

• 一般にy = x ^ (x << n)に対して(y >> n) ^ (y >> (n-1)) ^ ... ^ (y >> 1)で復元ができる。右シフトも同様。
• これはfor (i=1; i<32-n; i*=2) y = y << iでより効率的に計算することができる。

逆関数になっていないことについて

• TinyMTはS0の最上位bitが遷移関数内で捨てられており、実際は状態ベクトルは127次元しかない
• 記事ではS1の復元をps1 = s0として逆算を行っているが、実際はこれでは最上位bitの情報が復元されていない。
• xとs2まで復元できたら、ps1 = s0とする代わりにps1 = (s0 & 0x7FFFFFFF) ^ ((x ^ s2) & 0x80000000)とすれば、S1が完全に復元できる（つまり最上位bitはS0ではなくx ^ s2の最上位bitを使う）。
• 行列表現を作って逆行列を直接求める場合も、S0の最上位bitを削って127次元に落としてから逆行列を求めないと、S0の最上位bitを復元に使っている逆行列が得られてしまう場合があるので注意が必要。