数列比較のRolling Hashは危険だよという話
概要
- mod Rolling Hash が任意の基数で落ちる(数列比較の)問題が作れた。
- 基数を2つとってハッシュのペアで比較するか、もっと大きいmodを使おう。
Rolling Hashとは
- 文字列や整数列に対するハッシュ関数の一つ。以下では整数列のみを扱う。
- 法 と基数 を用いたときの、数列 に対するRolling Hash は次で定義される。
衝突確率
- 異なる数列が同じハッシュ値をとることを、ハッシュの衝突と呼ぶ。
法 が十分大きな素数のとき、長さ の数列 のハッシュが衝突するような基数 は高々 個しかない。
互いに異なる数列 のどこかで衝突が起こるような基数 は高々 個しかない。
法 とした場合、どんな基数 を取っても衝突してしまうケースがあるのではないか? そのような問題が構築できた。
問題の構築
アイデア
は を根に持つ。
- が の約数のときに限る。
- とおいた。
- を の原始根とした。
- は任意の整数。
証明
に対して
のとき、 となる(衝突する)。
- とおいた。
- とおいた。
証明
とおけば上の議論により直ちに結論を得る。
となるように をとれば、 が をカバーすることで でハッシュの衝突が生じる。 は原始根なので、これは任意の基数 で衝突が生じることを意味する。
仕上げ
- のとき、 程度にすれば とできる。
- をそのまま与えると、 入力サイズが 程度になってしまう。
- はほとんど で埋められた数列なので、情報量は小さい。
- クエリの問題にしてみる。各クエリで数列が編集されて、途中で出てきた数列の種類数を答えさせる。
完成した問題
- Input: 全て整数
L, Q k_1 v_1 ... k_Q v_Q
制約
Output
- 長さ の数列 ] を定義する。
- 数列 の 番目の要素を で置き換えた数列を とおく。
- 数列 は全部で何種類あるかを出力せよ。
mod Rolling Hash を落とすケース
の原始根 をとる。
が に、 が に対応している。