Pokémon RNG Advent Calendar 2016 13日目の記事です。疑似乱数TinyMTにおいて得られた乱数値から乱数生成器の状態を逆算する話です。SM孵化乱数列を計算する : ただの雑記byさきによってTinyMTのstateは連続した127個の乱数値の下位1bitがあれば得られるこ…

疑似乱数TinyMTの逆算について考えます。https://odanpoyo.github.io/2016/12/10/Tiny-Mersenne-twister%E3%81%AE%E9%80%86%E7%AE%97/の続きともいえるような内容です。 上の記事はstateから一つ前のstateを計算するという話でしたが、この記事では連続する4…

で与えられる線形合同法疑似乱数において、その上位16bit が観測できるという状況を考えます。 そのとき $X_0$ の値を求めるにはどうすればよいでしょうか。$Y_0$ を $\alpha$ とおくとき $X_0$ は とかけます。よって $2^{16}$ 通りの $x$ すべてをしらみつ…

この記事ではKnuthの補題Pと(Z/mZ)*の構造定理の補題 - oupoの日記で与えた補題を利用する．

“The Art of Computer Programming”において線形合同法に関する定理を証明するのに使われる補題Pの証明を記す．また整数論の教科書で(Z/mZ)*の構造を決定するのに用いられる補題 (補題2と補題4)が補題Pから導かれることを見る．