最下位bit列から状態を復元するアルゴリズムの実装

具体的にはどうすればいいの？って話です。
つい最近、実用方面でも重要になりましたね。

数年前に書いた記事では計算をこねくり回していましたが、要するに『最下位bitの生成に使われる係数列は行列の最下段』であることと、『それを並べた行列が「128回分の最下位bit列をベクトルとして生成する」行列になること』、そしてその行列が可逆であることが重要なので、各基底

ω_{0}, ω_{1}, \dots, ω_{127}

について

T^{i}

を作用させたベクトルを並べて行列を作り、その逆行列を求めればよいことになる。

\begin{aligned} [\begin{array}{c} y_{0} \\ y_{1} \\ ⋮ \\ y_{127} \end{array}] & = [\begin{array}{c} a_{0 0} & a_{0 1} & \dots & a_{0 127} \\ a_{1 0} & a_{1 1} & \dots & a_{1 127} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{127 0} & a_{127 1} & \dots & a_{127 127} \end{array}] [\begin{array}{c} x_{0} \\ x_{1} \\ ⋮ \\ x_{127} \end{array}] \end{aligned}

のとき、

\begin{aligned} y_{0} & = [\begin{array}{c} a_{0 0} & a_{0 1} & \dots & a_{0 127} \end{array}] [\begin{array}{c} x_{0} \\ x_{1} \\ ⋮ \\ x_{127} \end{array}] \\ (= a_{0 0} x_{0} + a_{0 1} x_{1} + \dots + a_{0 127} x_{127}) \end{aligned}

で、この

(a_{0 0}, a_{0 1}, \dots, a_{0 127})

が、元の行列のうち、『次の内部状態の最下位bitの生成に関わる部分』のすべてになります。この

(a_{i 0}, a_{i 1}, \dots, a_{i 127})

を128個集めて並べ、行列を作るのが目標です。

しかし、今行列として表現されている

T

は、処理上はビット整数に対するビットローテートやxorとして表現されており、行列として表しなおすのは得策ではありません。

そこで、遷移関数を作用させて得られる値(=更新後の内部状態)を使って

(a_{i 0}, a_{i 1}, \dots, a_{i 127})

を得ることを考えます。

ここでベクトル空間の性質が活きます。

[\begin{matrix} x_{0} \\ x_{1} \\ ⋮ \\ x_{127} \end{matrix}] = [\begin{matrix} x_{0} \\ 0 \\ ⋮ \\ 0 \end{matrix}] + [\begin{matrix} 0 \\ x_{1} \\ ⋮ \\ 0 \end{matrix}] + \dots + [\begin{matrix} 0 \\ 0 \\ ⋮ \\ x_{127} \end{matrix}]

と分解することができます(以下、

x_{i}

以外の要素が

0

になっているベクトルを

x_{i}^{'}

と表します)。さらに、これら個々に遷移関数を作用させた結果を足し合わせれば、

x

に遷移関数を作用させたのと同じく

y

になるのです。
ベクトルの和は各成分ごとの和になるので、各

f (x_{i}^{'})

の第0成分を足し合わせれば

y_{0}

が得られることになります。これは

f^{2}, f^{3} \dots

についても同様です。

以上を実装したものがこちら。