[6303] in cryptography@c2.net mail archive
Re: rate of finding collisions
daemon@ATHENA.MIT.EDU (Paul Crowley)
Mon Jan 3 13:01:18 2000
To: iang@cs.berkeley.edu (Ian Goldberg)
Cc: cryptography@c2.net
From: Paul Crowley <paul@hedonism.demon.co.uk>
Date: 03 Jan 2000 12:41:23 +0000
In-Reply-To: iang@cs.berkeley.edu's message of "1 Dec 1999 20:18:39 GMT"
Message-ID: <87embzmioc.fsf@hedonism.demon.co.uk>
iang@cs.berkeley.edu (Ian Goldberg) writes:
> The expected number of collisions you get if you sample S items out of
> a universe of size U (=2^N in the above case) is about (S^2)/U.
I know this is a month old but I'm only now catching up on the
newsgroup. I'd be surprised if the expected number isn't about
(S^2)/2U where S is large but much smaller than U. Where S is small
you have to use S(S-1)/2U. The source of error in this reckoning is
that you treat every pair of members of S as independent, but it's
very small when U is much bigger than S.
If the expected number of collisions is x, the probability of *no*
collisions is I think roughly e^-x.
If I keep generating new members of S from U until I get a collision,
does anyone know the expected size of S when I succeed?
--
__
\/ o\ paul@hedonism.demon.co.uk Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
