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

[逆関数の考察](https://hackmd.io/@yatsuna827/r1ez2-n3S)

[復元が可能であることの数学的な保証](https://oupo.hatenadiary.com/entry/20171221/1513832608)

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

数年前に書いた記事では計算をこねくり回していましたが、要するに『最下位bitの生成に使われる係数列は行列の最下段』であることと、『それを並べた行列が「128回分の最下位bit列をベクトルとして生成する」行列になること』、そしてその行列が可逆であることが重要なので、各基底$\omega_0,\ \omega_1,\ \cdots,\ \omega_{127}$について$T^i$を作用させたベクトルを並べて行列を作り、その逆行列を求めればよいことになる。

$\begin{align}
\begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{127} \end{bmatrix}
&= \begin{bmatrix} a_{0\ 0} & a_{0\ 1} & \cdots & a_{0\ 127}\\ a_{1\ 0} & a_{1\ 1} & \cdots & a_{1\ 127} \\ \vdots & \vdots & \ddots & \vdots \\ a_{127\ 0} & a_{127\ 1} & \cdots & a_{127\ 127}\end{bmatrix} \begin{bmatrix} x_{0} \\ x_{1} \\ \vdots \\ x_{127} \end{bmatrix}
\end{align}$

のとき、

$\begin{align}
y_{0}
&= \begin{bmatrix} a_{0\ 0} & a_{0\ 1} & \cdots & a_{0\ 127}\end{bmatrix} \begin{bmatrix} x_{0} \\ x_{1} \\ \vdots \\ x_{127} \end{bmatrix} \\
&(= a_{0\ 0}x_0 + a_{0\ 1}x_1 + \cdots + a_{0\ 127}x_{127})
\end{align}$

で、この$(a_{0\ 0},\ a_{0\ 1}, \ \cdots,\ a_{0\ 127})$が、元の行列のうち、『次の内部状態の最下位bitの生成に関わる部分』のすべてになります。この$(a_{i\ 0},\ a_{i\ 1}, \ \cdots,\ a_{i\ 127})$を128個集めて並べ、行列を作るのが目標です。

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

そこで、遷移関数を作用させて得られる値(=更新後の内部状態)を使って$(a_{i\ 0},\ a_{i\ 1}, \ \cdots,\ a_{i\ 127})$を得ることを考えます。

ここでベクトル空間の性質が活きます。$$\begin{bmatrix} x_{0} \\ x_{1} \\ \vdots \\ x_{127} \end{bmatrix}=\begin{bmatrix} x_{0} \\ 0 \\ \vdots \\ 0 \end{bmatrix}+\begin{bmatrix} 0 \\ x_{1} \\ \vdots \\ 0 \end{bmatrix}+\cdots+\begin{bmatrix} 0 \\ 0 \\ \vdots \\ x_{127} \end{bmatrix}$$
と分解することができます(以下、$x_i$以外の要素が$0$になっているベクトルを${\bf x}_i^\prime$と表します)。さらに、これら個々に遷移関数を作用させた結果を足し合わせれば、${\bf x}$に遷移関数を作用させたのと同じく${\bf y}$になるのです。
ベクトルの和は各成分ごとの和になるので、各$f({\bf x}_i^\prime)$の第0成分を足し合わせれば$y_0$が得られることになります。これは$f^2,\ f^3\, \cdots$についても同様です。

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

[最初に実装したやつ(gist)](https://gist.github.com/yatsuna827/6e8d717df41960f265a4c3de46a0af7c)

[SwShRNGLibraryに組み込んだやつ、前処理が不要なので実行速度的にはたぶんこっちのほうが有利(github)](https://github.com/yatsuna827/SwShRNGLirary/blob/master/SwShRNGLibrary/XoroshiroReverse.cs)