# xoroshiro128+の状態遷移の逆算の考察
## はじめに
この記事は[Pokémon Past Generation Advent Calender 2019](https://adventar.org/calendars/4435) 一日目の記事です.

## なんぞこれ？
- 某所で話題になっている疑似乱数生成器"xoroshiro128+"の状態遷移の逆関数を求めてみようという趣旨の記事です.

## 逆関数が求まると何がうれしいの？
- 初期seedを逆算したりできて色々と便利.
- 線形代数の計算を実用的な場面で行えるので楽しい(過程が).

## xoroshiroの状態遷移の概要
- xoroshiroは"xor","rotate","shift","rotate"の略らしいです. xorshiftの改良版だとか.
- xorとビットシフトは乱数調整で遊んでいる人ならよく知っているはずなので省略しますが, rotateはあんまりなじみがないかもしれません. 普通のビットシフトは端からあふれ出たビットは捨てられますが, rotateは逆の端からﾆｭｯと出てきます.
- `1011`を左に2bit shiftをかけると`1100`になりますが, rotateだと`1110`になります.
- xoroshito128+は128bitの内部状態を64bit×2で持ち, 64bitの乱数値を返してくれます.
- 内部状態を64bit整数`X`,`Y`で持っているとすると, `X+Y`で乱数を取得します. MTみたいなtemperingは無い様子.
- 状態遷移は以下の通りの処理で行われます.

X = rotl(X, 24) ^ (X^Y) ^ ((X^Y) << 16)
Y = rotl(X^Y, 37)

## 方針
- [これ](http://yatsuna-827.hatenadiary.com/entry/2017/12/26/050359)と全く一緒. xorとshiftしか使ってない乱数生成器なら全部同じ方針で解けると思います.

## 実際に計算してみる
(以下常体)

`rotl(X,n)` =: $R_l(n) \in M_{64}({\bf F}_2),$
`<<16` =: $L_{16} \in M_{64}({\bf F}_2)$とおいて,
$x_n,y_n \in {\bf F}_2^{64}$を内部状態`X,Y`とする.

$\begin{align}
\begin{bmatrix} x_{n+1} \\ y_{n+1} \end{bmatrix}
&= \begin{bmatrix} R_l(24)x_n + x_n+y_n+L_{16}(x_n+y_n)\\ R_l(37)(x_y+y_n) \end{bmatrix} \\
&= \begin{bmatrix} (R_l(24)+E+L_{16})x_n+(E+L_{16})y_n\\ R_l(37)x_y+R_l(37)y_n \end{bmatrix} \\
&= \begin{bmatrix} R_l(24)+E+L_{16} & E+L_{16} \\ R_l(37) & R_l(37) \end{bmatrix}
\begin{bmatrix} x_n \\ y_n \end{bmatrix}.
\end{align}$

$R_l(n) \in GL_{64}({\bf F}_2)$で, $R_l(n)^{-1} = R_l(64-n)$であり, $L'_{16}:=E+L_{16}$についても, ${\bf F}_2^{64}$においては$b=a+(a<<n) \iff a=b+(a<<n)$であることに注意すると, $x,y$の第 $i$ bitをそれぞれ$x_i,y_i$とするとき
$x_i = \begin{cases} y_i \quad (1\leq i<n) \\ y_i+x_{i-n} \quad (n \leq i \leq 64) \end{cases}$
であることから, 可逆であることがわかる. あとは頑張れば逆行列が出る.

簡単のため$R_l(24)=A, L'_{16}=B, R_l(37)=C$とおくと,

$\begin{bmatrix} x_{n+1} \\ y_{n+1} \end{bmatrix}= \begin{bmatrix} A+B & B \\ C & C \end{bmatrix}\begin{bmatrix}x_n \\ y_n \end{bmatrix}$

と書けてとてもうれしい. これの逆行列を求める.

$\begin{bmatrix} A+B & B \\ C & C \end{bmatrix}\begin{bmatrix} X_1 & X_2 \\ X_3 & X_4 \end{bmatrix}= \begin{bmatrix} E & 0 \\ 0 & E \end{bmatrix}$

とすると,

$\begin{align}
(A+B)X_1+BX_3 &= E\\
(A+B)X_2+BX_4 &= 0\\
CX_1+CX_3 &= 0\\
CX_2+CX_4 &= E
\end{align}$

の4本の式が立つ. $A,B,C \in M_{64}({\bf F}_2)$なので$-X=X$であることと, 乗法が非可換であることに注意してこれを解いていく.

下の2本の式より

$X_3=X_1 \\
X_4=C^{-1}+X_1.$

これを上の2本にそれぞれ代入していく. まず1本目から

$\begin{align}
(A+B)X_1+BX_1 &= E \\
AX_1+BX_1+BX_1 &= E \\
AX_1 &= E \\
X_1 &= A^{-1}.
\end{align}$
よって, $X_1=X_3=A^{-1}.$

次に2本目から

$\begin{align}
(A+B)X_2+B(C^{-1}+X_2) &= 0 \\
AX_2+BX_2+BC^{-1}+BX_2 &= 0 \\
AX_2+BC^{-1} &= 0 \\
AX_2 &= BC^{-1} \\
X_2 &= A^{-1}BC^{-1}.
\end{align}$

よって$X_2=A^{-1}BC^{-1}, X_4 = A^{-1}BC^{-1}+C^{-1}.$

以上から,

$\begin{align}
\begin{bmatrix} A+B & B \\ C & C \end{bmatrix}^{-1}
&= \begin{bmatrix} A^{-1} & A^{-1}BC^{-1} \\ A^{-1} & A^{-1}BC^{-1}+C^{-1} \end{bmatrix} \\
&= \begin{bmatrix} R_l(24)^{-1} & R_l(24)^{-1}L'_{16}R_l(37)^{-1} \\ R_l(24)^{-1} & R_l(24)^{-1}L'_{16}R_l(37)^{-1}+R_l(37)^{-1} \end{bmatrix} \\
&= \begin{bmatrix} R_l(40) & R_l(40)L'_{16}R_l(27) \\ R_l(40) & R_l(40)L'_{16}R_l(27)+R_l(27) \end{bmatrix}.
\end{align}$

($L'_{16}$の可逆性必要なかった……)

すなわち,

$\begin{bmatrix} x_n \\ y_n \end{bmatrix}= \begin{bmatrix} R_l(40) & R_l(40)L'_{16}R_l(27) \\ R_l(40) & R_l(40)L'_{16}R_l(27)+R_l(27) \end{bmatrix}\begin{bmatrix}x_{n+1} \\ y_{n+1} \end{bmatrix}$

$\begin{align}
x_n &= R_l(40)x_{n+1}+R_l(40)(E+L_{16})R_l(27)y_{n+1}\\
&= R_l(40)x_{n+1}+R_l(3)y_{n+1}+R_l(40)L_{16}R_l(27)y_{n+1} \\
y_n &= R_l(40)x_{n+1}+R_l(40)(E+L_{16})R_l(27)y_{n+1}+R_l(27)y_{n+1}\\
&= R_l(40)x_{n+1}+R_l(3)y_{n+1}+R_l(40)L_{16}R_l(27)y_{n+1}+R_l(27)y_{n+1}.
\end{align}$

以上から,

X = rotl(X,40) ^ rotl(Y,3) ^ rotl((rotl(Y,27)<<16),40)
Y = rotl(X,40) ^ rotl(Y,3) ^ rotl((rotl(Y,27)<<16),40) ^ rotl(Y,27)

で逆算ができる.

(https://gist.github.com/yatsuna827/ea985d2ce4d34da1e35ec4adf1862050)

## さいごに
明日も私の記事ですね.
まだたくさん空きがあるので参加お待ちしています.