Xorshift128の遷移行列とその逆行列を考える

数学を専攻してらっしゃる方からすると, 色々ツッコミどころ満載かと思いますがご容赦ください.

準備

Xorshift128は, その名前の通り128bit(32bit

$\times 4$)からなる内部状態をxor演算とシフト演算によって更新することで乱数を生成しています.

まずは, 内部状態の更新を行列で表してみましょう. (以降の行列表現は全てベクトルに対して左側から作用させるものとします)

$k$ビットだけ左シフトする演算

$L_k$(あるいは右シフトする演算

$R_k$)は行列を用いて次のように書けます.

$$\begin{array}{r}(L_k{)}_{i,j}=\{\begin{array}{ll}1& (i=j-k)\\ 0& (otherwise)\end{array}\\ (R_k{)}_{i,j}=\{\begin{array}{ll}1& (i=j+k)\\ 0& (otherwise)\end{array}\end{array}$$
また, xorは

${\mathbb{F}}_2$上の加法として表現できます.

遷移行列の生成

Xorshift128の内部状態を

$\text{boldsymbol}{r}_n\in {\mathbb{F}}_2^{128}$と表すことにします.

$\text{boldsymbol}{r}_n$を

$\text{boldsymbol}{r}_{n+1}$に更新する遷移行列

$T$(すなわち,

$\text{boldsymbol}{r}_{n+1}=T\text{boldsymbol}{r}_n$を満たす

$T$)は,

$32\times 32$の小行列によるブロック分割によって

$$\begin{array}{r}T=\left(\begin{array}{cccc}\mathcal{O}& E& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& E& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& \mathcal{O}& E\\ P& \mathcal{O}& \mathcal{O}& Q\end{array}\right)\end{array}$$
と書けます. ここで,

$P,Q$をそれぞれ

$P=(E+R_8)(E+L_{11}),Q=(E+R_{19})$とします.

逆行列の生成

さて, 本題である

$T$の逆行列

$T^{-1}$を考えることにしましょう. 先ほどと同様に

$32\times 32$の小行列によるブロック分割で考えると,

$$\begin{array}{r}{T}^{-1}=\left(\begin{array}{cccc}A& B& C& D\\ E& \mathcal{O}& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& E& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& E& \mathcal{O}\end{array}\right)\end{array}$$
として表せそうです. 逆行列の性質を用いれば,

$$\begin{array}{rl}T{T}^{-1}& =\left(\begin{array}{cccc}\mathcal{O}& E& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& E& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& \mathcal{O}& E\\ P& \mathcal{O}& \mathcal{O}& Q\end{array}\right)\left(\begin{array}{cccc}A& B& C& D\\ E& \mathcal{O}& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& E& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& E& \mathcal{O}\end{array}\right)\\ & =\left(\begin{array}{cccc}E& \mathcal{O}& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& E& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& E& \mathcal{O}\\ PA& PB& PC+Q& PD\end{array}\right)\\ & =\left(\begin{array}{cccc}E& \mathcal{O}& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& E& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& E& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& \mathcal{O}& E\end{array}\right)=E\end{array}$$
を満たすはずです. 従って,

$$\begin{array}{r}\{\begin{array}{l}PA=\mathcal{O}\\ PB=\mathcal{O}\\ PC+Q=\mathcal{O}\\ PD=E\end{array}\end{array}$$
の4本の式が立つことから, 各

$A,B,C,D$について解くと,

$$\begin{array}{r}A=\mathcal{O}\\ B=\mathcal{O}\\ C=P^{-1}Q\\ D=P^{-1}\end{array}$$
が得られました. 以上より,

$$\begin{array}{r}{T}^{-1}=\left(\begin{array}{cccc}\mathcal{O}& \mathcal{O}& P^{-1}Q& P^{-1}\\ E& \mathcal{O}& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& E& \mathcal{O}& \mathcal{O}\\ \mathcal{O}& \mathcal{O}& E& \mathcal{O}\end{array}\right)\end{array}$$
が導出されます.