關於生日問題的下界

我現在熟悉 Katz 和 Lindell 書中的定理 A.16 中揭示的生日問題的下限（或者參見此網頁）。

如果一個表示 $ C(q,N) $ 從一組大小中獲取獨立且均勻分佈的元素時的碰撞機率 $ N $ 邊界是通過假設獲得的 $ q \le \sqrt{2N} $ :

$ C(q,N) \ge \frac{q(q-1)}{4N} $

但是，我在課堂上的界限是（沒有不等式假設 $ q $ ):

$ \forall N \in \mathbb{N}.C(q,N) \ge \frac{(q-1)^2}{2N} $

我怎樣才能證明這個界限是正確的？

問題是 $ \displaystyle C(q,N) \ge \frac{(q-1)^2}{2N} $ 綁定是錯誤的。這與眾所周知的事實不相容 $ N=q^2 $ 和大， $ C(q,N)\approx1-e^{-1/2}\approx39.3% $ .

一個正確的界限是 $ \displaystyle C(q,N) \le \frac{(q-1),q}{2N} $ , 對所有人有效 $ q $ 和 $ N\ge1 $ , 緊的時候 $ q\ll\sqrt N $ .

另一個正確的界限是 $ \displaystyle C(q,N) \ge \frac{(q-1)^2}{4N} $ 什麼時候 $ 1\le q\le\sqrt{2N} $ ，這來自問題的引理。

有關一些推導，請參閱此答案，但請注意那裡的符號 $ (n,k) $ 和 $ p_n $ 問題在哪裡 $ (q,N) $ 和 $ C(q,N) $ .

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