# 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?

-
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

1
– cardinal Sep 14 '11 at 10:15

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 1 Answer

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$.

-

The ln function is great, I never thought it could be this easy. Thank you for your steps. – Donaldt Fourier Sep 16 '11 at 1:16
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 6, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9513722658157349, "perplexity_flag": "middle"}