问题描述

给定 \(n\) 个人，一年有 \(m\) 天，为了使得至少有两人生日相同的概率大于等于 \(\epsilon\)，计算 \(n\) 的大小

推导

设 \(P(n,\ m)\) 表示至少两个人生日相同的概率，则

\[\begin{aligned} P(n,\ m) & = 1 - \frac{A_{n}^{m}}{m^n}\\ & = 1 - \frac{1\cdot 2\cdots (m - n + 1)}{m^n}\\ & = 1 - (1 - \frac{1}{m})(1 - \frac{2}{m})\cdots (1 - \frac{n - 1}{m}) \end{aligned} \]

即

\[1 - P(n,\ m) = (1 - \frac{1}{m})(1 - \frac{2}{m})\cdots (1 - \frac{n - 1}{m}) \]

根据 \(1 + x\leq e^x\)，有 \(1 - \frac{i}{m}\leq e^{-\frac{i}{m}}\)，所以

\[1 - P(n,\ m)\leq \prod_{i = 1}^{n - 1}e^{-\frac{i}{m}} \]

在上式两边取对数，得到

\[ln(1 - P(n,\ m))\leq \sum_{i = 1}^{n - 1}(-\frac{i}{m}) = -\frac{n\cdot (n - 1)}{2m} \]

即

\[ln(1 - P(n,\ m))\leq -\frac{n(n - 1)}{2m} \]

令 \(P(n,\ m)\geq \epsilon,\ 0 < \epsilon < 1\)，则 \(ln(1 - P(n,\ m))\leq ln(1 - \epsilon)< -\epsilon\)，所以

\[-\epsilon\leq -\frac{n(n - 1)}{2m} \]

即

\[n^2 - n - 2m\epsilon\leq 0 \]

考虑上述一元二次不等式，判别式 \(\Delta = 1 + 8m\epsilon > 0\)，所以方程组有解，解的范围为

\[0 < n < \frac{1 + \sqrt{1 + 8m\epsilon}}{2} \]

所以

\[O(n) = O(\frac{1 + \sqrt{1 + 8m\epsilon}}{2}) = O(\sqrt{2m\epsilon}) = O(\sqrt{m}) \]

生日攻击

考虑一个哈希函数 \(f: D\rightarrow \left\{0,\ 1\right\}^{n}\)，哈希空间为 \(2^n\)，只需要 \(O(2^{\frac{n}{2}})\) 级别的哈希值便能构成碰撞