くじ用のシードを完全に特定するには最低何日分必要か調べてみた。
連続であることが前提ではあるが。
第4世代くじ番号についてはこちらに既に書かれている方が。
→http://d.hatena.ne.jp/oupo/20100316/1268730769
そんなわけで虱潰しでプログラム書いて計算した結果、計算が間違ってなければ3日あれば完全に特定できるよう。
2日で特定できるシードも52222/65536あって、残りの13314/65536は2つまでしか絞れないもの。
一応調べ方だけ簡単に書いておく。
くじ番号aが分かったときbを0～65535とするとくじ番号決定のときa*65536+bで与えられる。
リンク先のから計算すると、これに0x6C078965をかけて0xCA55F729を足すと次のくじ番号決定の時のが分かる。
aは固定であり、かつ下16bitに影響しないので、これをbについて適用していって同じになるものが存在するかを探した。
連続であることが前提ではあるが。
第4世代くじ番号についてはこちらに既に書かれている方が。
→http://d.hatena.ne.jp/oupo/20100316/1268730769
そんなわけで虱潰しでプログラム書いて計算した結果、計算が間違ってなければ3日あれば完全に特定できるよう。
2日で特定できるシードも52222/65536あって、残りの13314/65536は2つまでしか絞れないもの。
一応調べ方だけ簡単に書いておく。
くじ番号aが分かったときbを0～65535とするとくじ番号決定のときa*65536+bで与えられる。
リンク先のから計算すると、これに0x6C078965をかけて0xCA55F729を足すと次のくじ番号決定の時のが分かる。
aは固定であり、かつ下16bitに影響しないので、これをbについて適用していって同じになるものが存在するかを探した。
2^32個しらみ潰しで調べる必要はなくて2^16個で済むのですね。その根拠は次の通りだと認識しました。
2つのseed x, yについて1つ目の乱数が等しいことは、2つのseed (x+2^16 a), (y+2^16 a)で1つ目の乱数が等しいことに同値。aは任意の整数。これは1つ目だけでなく2つ目、3つ目、…でも同様。
つまり、たとえば0x00001111と0x00002222との1つ目の乱数が異なれば0xaaaa1111と0xaaaa2222との1つ目の乱数も異なる。
実際、seedがxのときの一つ目の乱数はfloor((Ax + B)/2^16) mod 2^16で得ることができて
floor((A(x + 2^16 a) + B)/2^16) ≡ floor((A(y + 2^16 a) + B)/2^16) (mod 2^16)
⇔ floor((Ax + B)/2^16) + aA ≡ floor((Ay + B)/2^16) + aA (mod 2^16)
⇔ floor((Ax + B)/2^16) ≡ floor((Ay + B)/2^16) (mod 2^16)
である。