Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
According to Wikipedia,
$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$
Let n(p; H) be the smallest number of values we have to choose, such that the probability for finding a collision is at least p. What if I wants my probability to be 1? In this case, $p = 1$ and $\frac{1}{1-1}$ is undefined. May I know how to find minimum number of values required to get a collision with the probability of 1 using the formula above?
To get a collision with probability 1, you need to hash $H+1$ distinct values. You can see that because it is possible that if you hash only $H$ values, each one might happen to hash to a unique hash output; if any reasonable sized hash function, this is extremely unlikely, but it does have a nonzero probability to happen. On the other hand, if we hash $H+1$ distinct values, we know (by the pigeon hole principle (because there are only $H$ hash outputs), that two of the inputs must hash to the same output.
The expressions on Wikipedia are probabilistic approximations and in any case look at the earlier approximation $$p\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^2/(2H)}$$ which shows you can achieve probability $1-\varepsilon$ for any $\varepsilon>0$ if you let $$e^{-n^2/(2H)}=\varepsilon$$ or $$n=\sqrt{2 H \ln (1/\varepsilon)}.$$
To guarantee a collision, you need $1+H$ distinct values by pigeonhole principle. It's much quicker to approach probability one than to guarantee it.
