Re: Is MD5 outdated ?

From: Pilou (pilou_at_kma.eu.org)
Date: 10/05/03 

Date: Sun, 05 Oct 2003 13:00:00 +0200

> 2**64.5 is 26087635650665564424.6991..., but if n is only
> 26087635650665564425, the probability is still less than 1/2, namely
> 0.49999999999999999999236.... Only when n is at least
> 26087635650665564426 is the probability greater than 1/2, namely
> 0.50000000000000000003069....
>
> Any number from +0.3009 to +1.3008 would have worked as well as +0.5,
> but 0.5 was a correct value that I could find without using a calculator.

Actually, as far as I can tell, your numbers are wrong.

Let f(k) = P(no collision with k people and 2^128 birthdays)

   f(26087635650665564425) =approx 0.367878

Let kk be the unique integer such that f(kk+1) < 0.5 < f(kk)

Let i = int(sqrt(2*ln(2)*n))

I can assure you that i-50 < kk < i+50

   i = 21719381355163562491 (approx 2^64.2356)