# BDSPのID調整でゴンベの瞬き間隔からPRNGの内部状態を復元する手法における誤差の取り扱いについての考察

---

以下、観測値(から元の乱数値を推定した値)を$x$、真値(0x7FFFFFで割る前の整数値)を$d$、想定される誤差の上界を$\varepsilon$と置く。ただし$x,d$は$23 {\rm bit}$の値として扱う(すなわち『最上位bit』と言えば第$22 {\rm bit}$を指す)。

---

先日、[ニアト氏によるゴンベの瞬きを利用したPRNGの内部状態の復元手法](https://hackmd.io/@niart/BJZc7whZ5)の解説が公開されました。

記事の通り、誤差範囲で上位bitに繰り上がりが発生している場合、真値として推定される値の上位bitが1通りに定まりません。しかしながら、繰り上がりが発生していればただちに得られる情報量がゼロになるわけでもありません。

たとえば観測値として得られた値が0x47FFFF(100 0111 1111 1111 1111 1111)である場合、真値は0x48XXXXの形である可能性がありますが、この場合でも上から3bitは観測値と同じく100になっています(第$19{\rm bit}$は確定することは出来ません)。

具体的には、区間$S$ = [0, 0x7FFFFF]を$2^i$等分するときの境界になる点の付近において、上から$i \ {\rm bit}$目以降が不確定になります。たとえば$S$の中央付近ではどのbitも不確定になりますし、$S$の左から$1/8$の位置(0xFFFFF)付近では第$20 {\rm bit}$より下は不確定になりますが、上の$2 {\rm bit}$は誤差の影響に依らず$00$で確定しています。

大雑把な説明図

すなわち、1回の瞬きから得る情報量を固定せずに考えれば、必要な観測回数を減らすことができ(ただし復元処理の実装はより複雑になるかもしれません)、また、十分な情報量を得るために必要な観測回数の期待値も計算できると思います(確率計算が苦手なのでやっていません)(誰か計算してください)。