[6167] in cryptography@c2.net mail archive
Re: rate of finding collisions
daemon@ATHENA.MIT.EDU (Matt Crawford)
Wed Dec 1 16:07:05 1999
Message-Id: <199912011950.NAA00134@gungnir.fnal.gov>
To: staym@accessdata.com
Cc: cryptography@c2.net
From: "Matt Crawford" <crawdad@fnal.gov>
In-reply-to: Your message of Wed, 01 Dec 1999 08:57:48 MST.
<3845457C.4E46@accessdata.com>
Date: Wed, 01 Dec 1999 13:50:09 -0600
> On average, you'll find one N-bit collision after looking at O(2^(N/2))
> random N-bit strings; how long does it take, on average, to find k
> collisions? O(k*2^(N/2))?
Assuming you mean k pairs, not one item repeated k times, I believe
the answer is sqrt(pi*N/2) * 2^(N/2).
Matt
