新しい数値設定や実装方法を提案するものではありません。
衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。
前提知識
本記事では簡単のため、アルファベットの集合を $\Sigma = \{0,1,\ldots,\sigma-1\}$ とします。英子文字であれば、ASCII コードによりアルファベットを $128$ 未満の整数に対応させたり、それをずらして $26$ 未満の整数に対応させることで、アルファベットを整数と見なせます。
Rolling Hash とは
Rolling Hash は、文字列 $S = S_0,S_1,S_2,\ldots$ を次のようにHash化する手法です：
【Rolling Hash】
法 $m$, 基数 $r$ を何らかの方法でとる。 文字列 $S = S_0,S_1,S_2,\ldots$ の Hash値 を$\mathrm{hash}(S) = \sum S_i r^i\pmod{m}$ と定める。
計算の容易さ、特に、適切な事前計算のもとで任意の部分文字列の Hash 値 が $1$ 件あたり $\Theta(1)$ 時間で計算できるところが優れています。この Hash 値 に対して、次を期待したいです。
【期待】
$\mathrm{hash}(S)$ は、$\pmod{m}$ でだいたいランダムだろう。したがって、文字列 $S, T$ $(S\neq T)$ に対して $\mathrm{hash}(S) = \mathrm{hash}(T)$ となる確率はだいたい $1/m$ だろう。
これは例えば、以下の条件下で正しいです。
- $r$ と $m$ は互いに素。
- $N$ を十分大きな自然数とし、$S$, $T$ は長さ $N$ 以下文字列全体から完全にランダムに選ばれる。
ところで、この主張の証明すら見たことがないように思うので、本記事の末尾に付録として記します。
敵対的な入力と、乱択アルゴリズム
この主張は正しいものの、それでもってこの Hash 関数の万能性を唱えることはできません。上の条件では、$S, T$ は任意のアルファベット列から完全ランダムに選ばれることを前提としています。しかし例えば、「世の中の書籍からランダムに選んだ長さ $N$ の文字列」といった状況では、入力文字列には何らかの偏りがあるはずです（例えば母音 a, i, u, e, o の出現割合が $1/\sigma$ より高くなります）。偏りのある文字列群に対しては、上記の確率解析は成り立つとは言えないことになります。
特にこのような確率解析では、worst case として、(敵対的な / 悪意ある) 入力に対する確率解析がしばしば議論となります。本記事でも、このことをテーマにしていきます。
【問題】
攻撃者は $m$, $r$ の選択アルゴリズムを確認した上で、文字列 $S$, $T$ $(S\neq T)$ を選べるものとする。$\mathrm{hash}(S) = \mathrm{hash}(T)$ となる確率を低く抑えよ（実現可能な確率について考察せよ）。
どんなに上手に値を決めようとも、使われている $m, r$ の値が固定されているとその時点で完全敗北します。ではどうするかというと、このような問題を解決する一般的な方法に 乱択アルゴリズム があります。特に、次の解決策について論じていきます。
【乱択アルゴリズム】
$m$ を事前に固定する。$0\leqq r < m$ をランダムにとる。この $m, r$ を使って Hash値を計算する。
乱択を用いることで、敵対的な攻撃者であっても意図した hash の衝突を起こすことは難しくなります。
基本的な評価
【定理１】
$m$ を素数として上の手法を用いると、どのような長さ $N$ の文字列 $S, T$ $(S\neq T)$ に対しても、$\mathrm{hash}(S) = \mathrm{hash}(T)$ となる確率は $\frac{N}{m}$ 以下である。
証明は次の通りです。
$\mathrm{hash(S)}$ はある多項式 $f_S$ の値 $f_S(r)$ に等しい。Hash の衝突が起こる条件は $f_S(r)-f_T(r) = 0$ のように書ける。$f = f_S-f_T$ は $0$ でない $N$ 次以下の多項式である。体において、$0$ でない $N$ 次以下の多項式は高々 $N$ 個以下の根しかもたないので、Hash が衝突する $r$ は $N$ 通り以下である。したがって、$r$ を乱択しておけば、その確率は $\frac{N}{m}$ 以下である。
注意1：
体において、$N$ 次多項式の根が $N$ 個以下であることは、因数定理から分かります。実数や複素数で証明をしたことがある人は、全く同じことが任意の体でできることを確認してください。$N$ 個の解があれば $f(x) = 0\iff c(x-a_1)\cdots(x-a_N) = 0$ のように変形できて、再び体であることから他の解の非存在が分かります。
注意2：
任意の環ではうそで、例えば環 $\Z/8\Z$ において $2$ 次方程式 $x^2 -1 = 0$ は $4$ つの解 $x=1,3,5,7$ を持ちます。
参考文献
（１）hos さん： ハッシュを衝突させる話
（２）eto_nagisa さん：Rolling Hashを殺す話
（２’）関連問題 → yukicoder No.3014 多項式ハッシュに関する教育的な問題
（３）keymoonさん：安全で爆速なRollingHashの話
以下、筆者なりに要点を挙げます。
（１）結論として、「$\pmod{2^{64}}$ の Rolling Hash は、基数 $r$ を乱択したとしても、確率 $1$ で衝突させることができる」ことが述べられています。上述の定理でいうところの「$m$ が素数」が欠けているため、多くの根を持つ多項式が構成できることが確認できます。良い Rolling Hash の条件として、法が素数であることが重要であることが確認できます。
（２）良い Rolling Hash に対する要請が、より具体的にまとまっています。$r$ を固定してしまうと、複数の Hash を併用しても攻撃されてしまうことが説明されています。さらに攻撃を行うための具体的なアルゴリズムまで詳しく説明されています。基数 $r$ を乱択することが重要であることが確認できます。
（３）以上の Rolling Hash に対する要請を満たした上で、64bit 整数の範囲でパフォーマンスの良い Rolling Hash を構成する方法が提案されています。良い実装を手に入れたいだけであれば、ここに挙げた中では最も近道であると思います。
衝突確率に対する詳しい考察（本記事の主題）
素数 $m$ を固定して $r$ を乱択した場合に、敵対的な入力に対する Hash の衝突確率を考察しましょう。この問題は、次のように書き換えることができます。
【問題】
$N$ 次多項式 $f = \sum_{i=0}^N a_i x^i$ （ただし $0\leqq |a_i| < \sigma$）を考える。$f\neq 0$ を上手くとって、なるべく多くの根を持つようにしたとき、根の個数 $\mathrm{root}(N)$を評価せよ。
この問題について、次の結果が得られたことを報告します。
【定理２】
次が成り立つ：
$$\biggl\lceil\frac{N+1}{\log_{\sigma}m}\biggr\rceil – 1 \leqq \mathrm{root}(N)\leqq N.$$
右辺は【定理１】による自明な評価です。左辺がこの記事の主結果で、「法を固定し、$r$ を乱択した」場合の非自明な性能限界を与えています。つまり、「固定 modと乱択した $r$」という手法を採用した時点で、衝突確率 $\frac{N+1}{m\log_{\sigma} m}$ 程度の攻撃を受け入れざるを得ないことが分かります。
証明をします。次のように集合 $A$, $A_+$ を定めます：$$A = \{f(x) = \sum_{i=0}^N a_ix^i\mid 0\leqq |a_i| < \sigma\},\qquad A_+ = \{f(x) = \sum_{i=0}^N a_ix^i\mid 0\leqq a_i < \sigma\}.$$
$k = \bigl\lceil\frac{N+1}{\log_{\sigma}m}\bigr\rceil – 1$ として、$k$ 個の根を持つ $f \in A\setminus \{0\}$ の存在を示せばよいです。特に、$r=0,1,\ldots, k-1$ に対して $f(r) = 0$ が成り立つような $f\in A \setminus \{0\} $ の存在を示します。
$\mathrm{eval}\colon A_+\longrightarrow (\Z/m\Z)^k$ を、$ \mathrm{eval}(f) = \bigl(f(0), f(1), \ldots, f(k-1)\bigr)$ により定めます。$|A_+| = \sigma^{N+1}$, $|(\Z/m\Z)^k| = m^k$ が成り立ち、さらに $k$ の取り方より $|A_+| > |(\Z/m\Z)^k|$ が成り立ちます。したがって、ある $f_1, f_2\in A$ （ただし $f_1\neq f_2$）が $ \mathrm{eval}(f_1) = \mathrm{eval}(f_2)$ を満たします。これらの差 $f = f_1 – f_2 \in A$ が条件を満たします。以上により存在が示されました。
注意：構成的ではない存在証明です。存在は証明されたものの、この証明方法に基づいた攻撃は困難かもしれません。
余談： https://yukicoder.me/problems/no/1017 を出題した翌日に、これが使える問題に遭遇したのでびっくりしました。
Appendix
本記事の冒頭で、敵対的な攻撃者が存在せず、入力が完全ランダムである場合には、次の期待が成り立つことを述べました。
【期待】
$\mathrm{hash}(S)$ は、$\pmod{m}$ でだいたいランダムだろう。したがって、文字列 $S, T$ $(S\neq T)$ に対して $\mathrm{hash}(S) = \mathrm{hash}(T)$ となる確率はだいたい $1/m$ だろう。
証明を与えます。これも証明を見たことがないような…？
【定理３】
互いに素な正の整数 $m, r$ を固定する。正の整数 $N$ をとり、$A_+ = \{f(x) = \sum_{i=0}^N a_ix^i\mid 0\leqq a_i < \sigma\}$ とおく。$N$ が十分大きいとき、$f\in A_+$ に対して $f(r)\in \Z/m\Z$ は均等に分布する。つまり、任意の $k$ に対して $\lim_{N\to\infty}\frac{|\{f\in A_+\mid f(r) = k\}|}{|A_+|} = \frac{1}{m}$ が成り立つ。
本記事ではおまけ扱いとしたいので、方針の説明くらいに留めます。ちょっと難しめの行間がありますがご了承ください。
$r^i \equiv 1\pmod{m}$ となる $i$ 全体の集合を $I$ として、$\sum_{i\in I} a_i$ が均等に分布することを示せばよいです。多項式を使ってこの分布を調べます。
$f = 1 + x + \dots + x^{\sigma-1}$ と十分大きな $N$ に対して、$\sum_{i\equiv k\pmod{m}}[x^i]f^N$ を評価すればよいです。$g = x^{m-k}f^N$ として、$\sum_{i\equiv 0\pmod{m}}[x^i]g$ を評価すればよいです。
この値は、$1$ の $m$ 乗根全体 $\mu_m = \{e^{2\pi i\cdot (j/m)}\in\C \mid 0\leqq j < m\}$ を用いて $\frac{1}{m}\sum_{\zeta\in \mu_m}g(\zeta)=\frac{1}{m}\sum_{\zeta}\zeta^{m-k}f(\zeta)^N$ と書くことができます。$N$ について、$f(\zeta)$ を公比とする等比数列の線形結合となります。複素絶対値 $|f(\zeta)|$ は $\zeta = 1$ のときにのみ最大値 $\sigma$ をとります。$N\to\infty$ の極限においてそれ以外の $\zeta$ の寄与は無視されて、$N\to\infty$ の極限における一様分布が従います。
参考
$0,1,\ldots, \sigma – 1$ を一様に動く確率変数 $X$ を $N$ 個足し合わせたものの確率分布を考えます。確率変数 $X$ に対して、そのモーメント母関数 $M_X(t) = E(e^{tX})$ あるいは 特性関数 $\phi_X(t) = M_X(it)$ を考えると、独立確率変数 $X_1, \ldots, X_N$ に対して $M_{X_1+\cdots+X_n}(t) = \prod_i M_{X_i}(t)$ が成り立つという性質があり、確率分布の畳み込みを分析する際の定跡手法となります（Fourier 変換とほぼ同じもので、関数の畳み込みが各点積に変換されます）。
今回の場合は、$N$ 個の和 $X = X_1 + \cdots + X_N$ が $\phi_X(t) = \phi _{X_1}(t)^N$ を満たすことからも、簡潔に $E(e^{i tX})$ （上述の $g(\zeta)$ に相当するもの）を計算することができます。
謝辞
議論や記事の詳細は、noshi91 さんと議論しながら完成させました。
