[6169] in cryptography@c2.net mail archive
Re: rate of finding collisions
daemon@ATHENA.MIT.EDU (Ian Goldberg)
Wed Dec 1 16:07:16 1999
To: cryptography@c2.net
From: iang@cs.berkeley.edu (Ian Goldberg)
Date: 1 Dec 1999 20:18:39 GMT
Message-ID: <823vqv$plq$1@abraham.cs.berkeley.edu>
In article <38454607.5504@accessdata.com>, <staym@accessdata.com> wrote:
>I wrote:
>>O(k*2^(N/2))?
>
>It has to be faster than that by a counting argument. How much faster?
O(sqrt(k * 2^N)) = O(sqrt(k) * 2^(N/2))
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.
- Ian
