[OT] Re: [ANN] MD5 1.0.2 Released (OT)

[Luis Carvalho <carvalho@...>]

> For how big a filesystem? If you have enough blocks, the probability
> of a collision will be 1.

If pc is the probability of collision ~ 1e-20, and n is the number of blocks,
then

p1 = P(at least one collision) = 1 - P(no collision) = 1 - (1 - pc)^c2(n),

where c2(n) is (n choose 2) = n*(n-1)/2, and assuming the collisions occur
independently. Since pc is small and n is large, p1 ~ 1 - exp(-c2(n)*pc).
Solving back for n, we get n ~ (1 + sqrt(1 - 8 * log(1 - p1) / pc)) / 2.
For p1 = 0.5, log10(n) = 10.07, and so I wouldn't risk playing with more than
tens of gigablocks. (If n = 1e11, p1 ~ 1.)

Cheers,
Luis.

-- 
A mathematician is a device for turning coffee into theorems.
        -- P. Erdos 

-- 
Luis Carvalho
Applied Math PhD Student - Brown University
PGP Key: E820854A <carvalho@dam.brown.edu>