N 個雜湊數字碰撞的機率

前 N 個雜湊數字碰撞的機率是多少？例如，我製作了一個腳本，將文件 sha1 雜湊的前 5 位數字附加到文件名。

那麼碰撞的機率會是 16^5=1048576 嗎？我是否正確計算了碰撞的機率。

生日問題是此類問題的通用名稱。你有 $ n $ 值，在大小空間中隨機均勻地選擇 $ t $ ; 這些值中至少有兩個相同的機率大致等於 $ n^2/(2t) $ . 什麼時候 $ n $ 變得接近 $ \sqrt{t} $ ，則機率急劇上升。在你的情況下，有 5 個十六進制數字，你有一個大小的空間 $ t = 16^5 $ ，所以平均而言，當你得到大約 1000 個值時，你可以期待你的第一次碰撞。

一種直覺的思考方式是 $ n $ 價值觀使 $ n^2/2 $ 對，並且，“不知何故”，每對都有機率 $ 1/t $ 是碰撞。（這對不是相互獨立的，但直覺在這種情況下仍然有效。）

引用自：https://crypto.stackexchange.com/questions/10400