# Birthday-paradox for big numbers and more than one person: Computing the approximate probability of $k$ hash collisions for $n$ hashes

Given a cryptographic hashing function, with say a $$256$$ bit-length, I want to calculate the probability that out of $$n$$ hashes we have at least $$k$$ hashes that collide in the first $$32$$-bit (assuming the $$n$$ hashes are uniformly distributed over all $$2^{32}$$ possible prefixes). Assume $$k$$ and $$n$$ are very high, something like $$k=2^{32},n=2^{64}$$. This reminds me of the birthday paradox but for more than $$2$$ people. I found this post, which suggest using an poisson approximation which from my understanding would result in the formula:

$$P(\text{at least k hashes in n trials share the same prefix}) =$$ $$1 - \exp \left (-{n \choose k}/(2^{32})^{(k-1)} \right )$$

because if we would check every combination of $$k$$ hashes in the set $$n$$ hashes, we would on average have $$\lambda = {n \choose k}/(2^{32})^{(k-1)}$$ combinations that share the same $$32$$ bit prefix.

The problem with that that formula is that the calculations take too long. For example, calculating the number $$(2^{32})^{2^{32}-1}$$ is simply too complex. Is there any other way I can approximate this probability while remaining in the computationally feasible area?

• Why do you think that it is complex? Apr 20, 2020 at 18:37
• @fgrieu do you mean $x^y=e^{y \ln x}$ Apr 20, 2020 at 19:41
• @kelalaka: yes.
– fgrieu
Apr 20, 2020 at 19:59
• @kelalaka I tried this NumberFormat[(2^32)^(2^32-1)] and this 1- e^(-Binomial[2**64,2**32]/((2^32)^(2^32-1))) in mathematica and it apparently exceeds the memory limit for my "basic plan". Python with the decimal package also takes too long for the calculations. Any software/bignum library you would recommend using for this? Apr 20, 2020 at 20:53
• @fgrieu Could you elaborate? How can I use that to simplify the formula? Apr 20, 2020 at 20:54

## 1 Answer

For large $$k$$ growing with $$n$$ the binomial coefficient needs to be approximated.

Let $$h(x)=-x\ln x-(1-x)\ln (1-x)$$ be the binary entropy function in nats, then for $$k\in [1,n-1]\cap \mathbb{Z}$$ we have $$\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)\}$$ where the upper bound approaches equality if $$k$$ and $$n-k$$ are both large. This is obtained from Stirling and then some other manipulation, and covers the whole range of $$k$$.

This result appears, e.g., in Bob Gallager's book Information Theory and Reliable Communications.

This will give a good approximation if you use the upper bound.

So, you have $$1-\exp\left[-\frac{\sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}}{\exp\{(k-1)\ln 2^{32}\}}\right]$$ and can further take differences of the exponential function arguments inside and simplify for $$n=2^{64},k=2^{32},$$ to $$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]$$ or $$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}} \exp\left(nh(2^{-32})-2^{32}\ln 2^{32}\right)\right]$$ and since for large $$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]$$