沒有碰撞的機率近似

我正在將沒有衝突的實際機率與“理解密碼學”文本中沒有衝突的機率近似公式進行比較。

近似值如下：

$$ P(\text{no collisions}) = \frac{e^{-t(t-1)}}{2 \cdot 2^n} $$ 我知道 t 代表元素的數量，但我對分母感到困惑。文中說 $ n $ 是輸出寬度 $ h() $ . 我真的不明白這一點。這是否意味著讓我們說生日悖論， $ n = 365 $ ? 所以分母是 $ 2 \cdot 2^{365} $ ?

對於具有 128 位輸出的雜湊函式，n=128。這樣的功能有 $ 2^{128} $ 可能的輸出。

對於生日悖論，您有 365 個不同的輸出，即 $ 2^n = 365 $ 或者 $ n = \log_2 {365} \approx 8.5 $ .

您還將找到此公式的替代版本，其中省略了2^公式中的部分： $ \frac{e^{-t(t-1)}}{2 \cdot N} $ . 在這種情況下，你會使用 $ N=365 $ 對於生日悖論和 $ N=2^{128} $ 對於 128 位雜湊。

如果 $ t $ 比較小 $ N=2^n $ ，公式可以近似為：

$$ 1-\frac{t(t-1)}{2}\frac{1}{ N}=1-\frac{1+2+3+…+(t-1)}{N}=1-(\frac{1}{N}+\frac{2}{N}+\frac{3}{N}+…+\frac{t-1}{N}) $$ 這很直覺，因為第一個值沒有碰撞的機會，第二個可以與 1 個現有值發生碰撞機率 $ \frac{1}{N} $ ，第三個可能與 2 個現有值發生碰撞機率 $ \frac{2}{N} $ ， ETC。

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