LCGにおけるseedの検索を離散幾何に帰着させる

LCG(線形合同法)でseedを検索することを離散幾何の問題に帰着させるということを考えてみました。

まず線形合同法の漸化式で使われる関数を(Ax + B) mod Mとしておきます。
seedを1増やしたとき、その一つ先のseedというのはA増えるか、A-M増えるかのどちらかです。
seedをsとして0からsまで1ずつ増やしていった間に一つ先のseedがA-M増えた回数をxとすると、1つ先のseedが0以上MAX以下であるというのは

 0 \leq B + As - Mx \leq \rm{MAX}

でかけます。

図を示すとこんな感じ。MAX = M/2としていて、黄色い領域が1つ先のseedが0以上MAX以下である範囲です。

これを使うと0以上MAX以下が2連続するseedというのは次の不等式を満たす格子点(s,x)に対するsの値となります。


 0 \leq s \leq \rm{MAX}
 0 \leq x
 0 \leq B + As - Mx \leq \rm{MAX}

このようにしてLCGのseedを探す問題を離散幾何の問題に帰着できました。
変数を3つに増やせばある範囲の値が3連続するseedというものも離散幾何の問題に書き直せます。4連続以上でも同様です。

では、既存の離散幾何のプログラムに、この帰着させた問題を解かせてみましょう。
線型不等式を満たす格子点の個数を求める「LattE」というプログラムがあります。

これを試してみたところ、M = 2^64, MAX = 2^48-1で2連続のseedの個数は一瞬 (0.01秒)で求まりました。
M, MAXは同じまま3連続にすると4.2秒。4連続にすると、いつ計算が終わるのかわからない感じだったので途中で中断。

これは3連続のときの画像。

もう一つ残念なことに、LattEは格子点の個数を求めることはできるものの、格子点を全て列挙することができない模様。
線型関数でコストを与えて、コストが最小な点を1個出力することはできるのですが、3連続の場合にそれをしてみても少し時間が経った後途中で落ちてしまいました。

LattEに与える入力ファイルを生成するプログラムはこちら

補足

不等式を満たす格子点(s,x)に対するsの値は解の候補であって、必ず解になるとは限らないのじゃないかと思われれるかもしれません。ところが実は必ず解になるのです。

それは(s,x)平面のs軸に垂直な直線lに対して2つの互いに平行な直線


 B + As - Mx = 0
 B + As - Mx = M

のそれぞれの交点の間の距離が1であること、したがってどんな定数s_0に対しても

 s = s_0
 0 \leq B + As - Mx \lt M

を満たす格子点(s,x)は1つしかないことからわかります。

筆者: oupo (連絡先: oupo.nejiki@gmail.com)