Calculating minimum number of messages hashed a 50% probability of a collision (Birthday Paradox) I encountered this while solving a crypto puzzle. This is the puzzle.
You have a hash which gives a 11-bit output. How many minimum messages do we have to hash to have a 50% probability of getting a collision.
Normally we see kind of problem being solved by using an approximation $2^{n/2}$ or $\sqrt {2^n}$
So for a 11-bit hash, the number of messages to hash to have 50% chance of a collision would be
$\sqrt {2^{11}} = 45.255 \approx 46$ messages
However, the solution for this puzzle uses
$log_{\frac {2^{11} - 1} {2^{11}}}{(0.5)} = log_{\frac{2047}{2048}}{(0.5)} = 1419.22 \approx 1420$ messages
So you have to hash approximately 1420 messages to get a 50% probability of having a collision.
The solution doesn't explain how they arrive at this. So which is the correct solution?
You are approximately correct; they are wrong. Their answer calculates the chance of matching a particular value i.e. hash inversion. To see this $k$ tries have a $(2047/2048)^k$ of failing to find a match so you want $k&gt;\log(0.5)/\log(2047/2048)$.
For small numbers we can calculate the exact value of the birthday bound by finding the smallest $k$ such that
$$\prod_{0\le i\le k}\frac{n-i}n=\frac {n!}{(n-k)!n^k}&lt;0.5$$
which in this case is $k=54$.