今さら感あふれる4GenLCGの性質のあれ
命題
第3第4世代のLCGにおいて、2つのSEED AとBに A xor B = 0x80000000 の関係があるとき
両者から順次生成される子SEED A(n)とB(n)の間にも
A(n) xor B(n) = 0x80000000の関係が成立することが実際の乱数列から推定できる。
証明
A xor B = 0x80000000 の関係が成立しているとき、SEED AとBの差異は最上位bitのみである。
このことから、SEED AとBのうち大きいほうをBとおくとB = A + 0x80000000 が成り立つ。
このとき、両者から生成される子SEED A(1)とB(1)を求めると
A(1) = A * 0x41c64e6d + 0x6073
B(1) = B * 0x41c64e6d + 0x6073
<=>B(1) = (A + 0x80000000) * 0x41c64e6d + 0x6073
<=>B(1) = A(1) + 0x80000000 * 0x41c64e6d ...(*)
ここで、LCGの定義から33bit以上は切り捨てられるので定数部分で実際に関与するのは 0x41c64e6d の最下位bitのみ(∵0x80000000 = 2^31)
計算すると 0x80000000 * 0x41c64e6d = 0x80000000 (mod 2^32) となり、
式(*)から B(1) = A(1) + 0x80000000 を得る。
ここで、A(1) xor B(1) = A(1) xor (A(1) xor 0x80000000) = 0x80000000 であり、
同様にして順次生成される子SEED A(n)とB(n)の間にも A(n) xor B(n) = 0x80000000 の関係が成立することが示された。
日本語が下手なのは許してください。。。