[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **[OT] Re: [ANN] MD5 1.0.2 Released (OT)**
**From**: Luis Carvalho <carvalho@...>
**Date**: Thu, 10 May 2007 10:51:32 -0400

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