大數字和不止一個人的生日悖論：計算ķķk雜湊衝突nnn雜湊
給定一個密碼散列函式，比如一個 $ 256 $ 位長，我想計算出的機率 $ n $ 我們至少有雜湊值 $ k $ 第一次碰撞的雜湊 $ 32 $ -位（假設 $ n $ 雜湊值均勻分佈在所有 $ 2^{32} $ 可能的前綴）。認為 $ k $ 和 $ n $ 非常高，比如 $ k=2^{32},n=2^{64} $ . 這讓我想起了生日悖論，但不止於此 $ 2 $ 人們。我找到了這篇文章，它建議使用Poisson近似值，據我所知，它會得出以下公式：
$$ P(\text{at least $k$ hashes in $n$ trials share the same prefix}) = $$ $$ 1 - \exp \left (-{n \choose k}/(2^{32})^{(k-1)} \right ) $$
因為如果我們檢查每一個組合 $ k $ 集合中的雜湊 $ n $ 雜湊，我們平均會有 $ \lambda = {n \choose k}/(2^{32})^{(k-1)} $ 共享相同的組合 $ 32 $ 位前綴。
該公式的問題在於計算時間太長。例如，計算數量 $ (2^{32})^{2^{32}-1} $ 簡直太複雜了。在保持在計算可行區域的同時，還有其他方法可以近似這個機率嗎？
對於大 $ k $ 與成長 $ n $ 二項式係數需要近似。
讓 $ h(x)=-x\ln x-(1-x)\ln (1-x) $ 是 nats 中的二元熵函式，則為 $ k\in [1,n-1]\cap \mathbb{Z} $ 我們有 $$ \sqrt{\frac{n}{8k(n-k)}}\exp{nh(k/n)} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp{nh(k/n)} $$ 如果上界接近相等，則 $ k $ 和 $ n-k $ 都很大。這是從斯特林獲得的，然後是其他一些操作，涵蓋了整個範圍 $ k $ .
例如，這個結果出現在 Bob Gallager 的著作Information Theory and Reliable Communications中。
如果您使用上限，這將給出一個很好的近似值。
所以你有了 $$ 1-\exp\left[-\frac{\sqrt{\frac{n}{2\pi k(n-k)}}\exp{nh(k/n)}}{\exp{(k-1)\ln 2^{32}}}\right] $$ 並且可以進一步取內部指數函式參數的差異並簡化為 $ n=2^{64},k=2^{32}, $ 至 $$ 1-\exp\left[-\sqrt{\frac{n}{2\pi k(n-k)}}\exp\left(nh(k/n)-(k-1)\ln 2^{32}\right)\right]\approx $$ $$ \approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(nh(1/k)-(k-1)\ln 2^{32}\right)\right] $$ 或者 $$ \approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(nh(2^{-32})-2^{32}\ln 2^{32}\right)\right] $$ 因為對於大 $ k $ , $ h(1/k)\approx \ln k, $ $$ \approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(n \ln 2^{32})-2^{32}\ln 2^{32}\right)\right] $$ $$ \approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left((2^{64}-2^{32}) \ln 2^{32}\right)\right]\approx $$ $$ \approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(2^{64} \times 32 \ln 2 \right)\right] $$