Re^2: On showing the weakness in the MD5 digest function and getting bitten by scalar context

[Velaki]

Not a paradox, merely simple probability. However, it does assume that people are born with equal likelihood throughout the year. But its solution will lead to the thought of a "paradox" in that the number of people that must be in the room seems less than what you'd expect. The trick here is whether you're looking for any two birthdays in the room to match, or a specific match to your own birthday. For this node, I will consider the former.

Something will happen, or it won't. There is a 100% chance of that, or we can say that the probability of something happening or not happening is 1.0, so we can say that the probability of people having the same birthday is 1 - "not the same birthday".

Why "not the same birthday" ? It's easier to compute. We can measure the probability of an event by looking at the the frequency with which the event may occur. This may be expressed as a simple ratio of the expected outcomes to the total possible outcomes, just like finding the probability of rolling a 7 on a pair of dice. 6 ways to make 7, and 36 possible outcomes of a pair of dice, for a probability of 1/6 for rolling a 7.

For the birthday problem, the probability may be measured by seeing how many ways we can have "not the same birthday" in the total number of possible days for the 23 people. More simply, we have 365 choices for a birthday. Since we want no overlap, we'll have 364 days left, then 363. Ultimately, we will have 365!/(365-n)! where n=number of people in the room.

Great, that's the number of ways we can "roll" the birthdays for n people. But what about the total number of ways for all people? We have 365 days for each person. So for n people, we have 365^n number of days.

Given this, we'll divide like in the dice problem, above, and see that the probability of "not the same birthday" for n people is (365!/(365-n)!)/(365^n). So, the probabilty of at least two people having the same birthday would be 1 - P("not the same birthday"), or 1 - ((365!/(365-n)!)/(365^n)).

For 23 people, this comes to 0.50729723432398540722541722833703, or just over 50%.

This would make a nice practice program, but you will probably need to use logarithms to perform the calculations if the numbers start to overflow.

Hope this helped,
-v

[perlfan]

Technically, you could find a collision in 1 try using a Monte Carlo method, i.e. random guessing. The change is extremely small, but not impossible. This is the case for *all* hashing no matter how large the hash space is.