Thom Brown wrote:
>> I'm not sure why you're saying that there's a 50%
>> chance of duplication after 7240 values though. With 33 million
>> combinations, I would have thought that duplications would become equally
>> likely at the 16,777,216 mark.
Basic probability.
<http://en.wikipedia.org/wiki/Birthday_attack>
<http://en.wikipedia.org/wiki/Birthday_problem>
Sam Mason wrote:
> No, that's why I pointed out birthday attacks---collisions happen much
> more often than you'd expect. Get 23 people in a room and you have a
> 50% chance of two people having the same birthday--not 150 people. This
> is why it's called the birthday attack and it's one of the basic tests
> for hash functions--any bias in their output will shrink this number
> even further.
Taking the birthday example, the chance that no two people in a group of size
n < 365 have the same birthday (irrespective of year) is
(365-0)/365 x (365-1)/365 x (365-2)/365 x (365-3)/365 ... x (365 - (n-1))/365
As each term in the expression is less than one, their multiplication together
rapidly approaches zero. That means the probability of two or more people
having the same birthday rapidly approaches one. The 50% point is a bit under
n=23.
Substitute 33 million for 365 for the OP's problem.
--
Lew
