32bit LCGのseedを手計算で求めよう (半分ネタ)

$X_{n+1} = (a X_n + b) \bmod 2^{32}$
　　　　 $a = \mathrm{0x41c64e6d},\;b = \mathrm{0x6073}$

で与えられる線形合同法疑似乱数において、その上位16bit

$Y_n = \lfloor X_n / 2^{16} \rfloor$

が観測できるという状況を考えます。
そのとき $X_0$ の値を求めるにはどうすればよいでしょうか。

$Y_0$ を $\alpha$ とおくとき $X_0$ は

$X_0 = 2^{16} \alpha + x,\;0 \le x < 2^{16}$

とかけます。よって $2^{16}$ 通りの $x$ すべてをしらみつぶして、 $Y_1$ の値が一致するものを調べればよさそうです。$Y_1$ の値が一致するものは複数個ある可能性がある場合があるのでその場合は $Y_2$ の値を調べます。これで疑似乱数のseedを特定できるでしょう。

しかし、$2^{16}$ 通り調べるのは手計算ではできないですね。
そこで手計算できる方法を考えます。

まず、

$X_{n+2^{16}} = (\mathrm{0xdfa40001} X_n + \mathrm{0x47310000}) \bmod 2^{32}$

であることに注意します。
特に係数がそれぞれ $2^{16}$ の倍数に1足した値と$2^{16}$ の倍数になっているので、それらを$2^{16} A + 1$, $2^{16} B$とおいてみます。

すると上の $X_0$ の候補の値について

$\begin{align*} X_{2^{16}} &= (2^{16} A + 1) (2^{16} \alpha + x) + 2^{16} B \\ &= 2^{16}(Ax+\alpha+B) + x\end{align}$

が成り立ちます。ここで $Y_{2^{16}}$ を $\beta$ とおけば

$Ax+\alpha+B \equiv \beta \pmod{2^{16}}$

なのでこれを解くことにより $x$ を得ます！
ただし $A$ は4の倍数になっているので、得られるのは $x \bmod 2^{14}$ です。したがってこの方法で得られるseedは4通りあるので、その後 $Y_1$ などを使って一通りに絞らないといけません。

上の方法をまとめると

1) 乱数を1つ生成し、その値(16bit)を得る ($\alpha$ とする)
2) 乱数を2^{16}-1 = 65535個進める
3) 乱数を1つ生成し、その値(16bit)を得る ($\beta$ とする)
4) $\alpha$ と $\beta$ からseedが4通りに絞れる

となります。

さて、よく見ると 0xdfa40001 は 2^{16} の倍数 + 1 であるだけでなく、 2^{18} の倍数 + 1 です。ここに気付くと上の方法は改良できます。
2^{16}個先を考えるのではなく2^{14}個先を考えるのです。

$X_{n+2^{14}} = (\mathrm{0xf7e90001} X_n + \mathrm{0xf1cc4000}) \bmod 2^{32}$

ここに出てくる係数をあらためて $2^{16} A + 1 = 0xf7e90001, 2^{14} B = 0xf1cc4000$ とおきます。

すると $X_0$ の候補の値について

$\begin{align*} X_{2^{14}} &= (2^{16} A + 1) (2^{16} \alpha + x) + 2^{14} B \\ &= 2^{14}(4Ax+4\alpha+B) + x\end{align}$

が成り立ちます。ここで $X_{2^{14}}$ を $2^{16} \beta + y$ とおけば

$\begin{align*} 2^{14}(4Ax+4\alpha+B)+x = 2^{16} \beta + y.\end{align}$

$x = 2^{14} x' + x'', y = 2^{14} y' + y'', 0 \ge x', y' < 4, 0 \ge x'', y'' < 2^{14}$ とおけば

$\begin{align*} 2^{14}(4Ax+4\alpha+B+x')+x'' = 2^{14} (4 \beta + y') + y''.\end{align}$

上位18bitをとることにより

$4Ax+4\alpha+B + x' \equiv 4 \beta + y' \pmod{2^{18}}$

$y' - x' = \delta$とけば

$4Ax+4\alpha+B \equiv 4 \beta + \delta \pmod{2^{18}}$ (1)
　　　　 $-4 < \delta < 4$

この式に適する$\delta$を選び、$x$について解くと解の候補が得られます。$x$と$\delta$の整合性をチェックし、解になっているか確かめられます。

上の方法をまとめると

1) 乱数を1つ生成し、その値(16bit)を得る ($\alpha$ とする)
2) 乱数を2^{14}-1 = 16383個進める
3) 乱数を1つ生成し、その値(16bit)を得る ($\beta$ とする)
4) $\alpha$ と $\beta$ からseedが最大2通り(最小0通り)に決定される

となります。

試しにやってみましょう。$\alpha = 11111, \beta = 22222$としてみます。
式(1)は

$253860x+44444+247601 \equiv 88888 + \delta \pmod{2^{18}}$
です。整理すると
$253860x \equiv -203157 + \delta \pmod{2^{18}}.$
$-203157 + \delta$は4の倍数にならざるを得ないことから$\delta = 1, -3$です。

$\delta = 1$のとき：

$253860x \equiv -203156 \pmod{2^{18}}.$
両辺を4で割り、
$63465x \equiv -50789 \pmod{2^{16}}.$
63465の2^{16}を法とした逆元はユークリッドの互除法により20569と求まるので
$x \equiv 20569 \cdot (-50789) \pmod{2^{16}}.$
計算すると
$x \equiv 30435 \pmod{2^{16}}$
と求まります。
このとき$x' = 1$なので$\delta = 1$と整合します（$\delta = y' - x'$をみたす$0 \ge y' < 4$があります）。

$\delta = -3$のとき：
同様の計算で

$x \equiv 51004 \pmod{2^{16}}$
と求まります。
このとき$x' = 3$なので$\delta = 1$と整合しません（$\delta = y' - x'$をみたす$0 \ge y' < 4$がありません）。

よって解は30435の一つです。
ゆえにseedは $2^{16} \cdot 11111 + 30435 = 728200931 = \mathrm{0x2b6776e3}$ です。

2^{14}回乱数を進めるなんて2^{16}通り機械でしらみつぶしするよりずっと大変じゃないかということで、半分ネタ記事でした。

追記 (2016/12/8)

2^{14}の方で必ず解が一通りになるという勘違いをしていてその間違いを残したまま公開していました。現在は修正済みです。