ろいしんぶろぐ

乱数調整とか

今さら感あふれる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 の関係が成立することが示された。

 

日本語が下手なのは許してください。。。