Re: rate of finding collisions

[Matt Crawford]

> 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