# Birthday attack/problem, calculate exact numbers? [duplicate]

Possible Duplicate:
Birthday-coverage problem

An example of what I wish to do is the following: http://stackoverflow.com/questions/4681913/substr-md5-collision/4785456#4785456

How would I calculate how many people would be required, as in the link above, to reach 50% or 0.001% or n% probability of collision exactly?

I am able to calculate the likelyhood of a collision in say a hash, with

$1-e^\frac{-n^2}{(2*10^6)}$

10^6 being six numerical digits from zero to nine. However, I would have to guess a lot of times before I got the exact number of people it would take to reach exactly 50%, which may be a fraction (i.e. 20.2 people)

How would I be able to find this?

-

## marked as duplicate by Qiaochu YuanSep 14 '11 at 15:38

Are you assuming that birthdates are uniformly-distributed? There is data that leads to reasonably questioning this belief/assumption. –  gary Sep 14 '11 at 4:29
See this question, where exact calculations, very tight approximations, hard bounds, and the expected value can all be found in the various answers. –  cardinal Sep 14 '11 at 10:15

I'm somewhat confused by the question because it contains the word "exact" four times but you suggest to calculate the probability of a collision using a relatively simple approximation. For this answer, I'll assume that you're aware that there are better approximations for this probability, and of the various answers you get by searching for "birthday" on this site, and that your question is only about calculating $n$ given $1-\exp(-n^2/(2k))$. This you can do by solving for $n$ as follows:
$$p=1-\mathrm e^{-n^2/2k}\;,$$ $$\mathrm e^{-n^2/2k}=1-p\;,$$ $$-\frac{n^2}{2k}=\log(1-p)\;,$$ $$n^2=-2k\log(1-p)\;,$$ $$n=\sqrt{2k\log(1-p)}\;,$$
where $\log$ is the natural logarithm, i. e. the logarithm to base $\mathrm e$.