How much work is required to find multiple collisions for a hash function? Assume an ideal hash function of output size n bits, finding one collision requires approximately 2^(n/2) evaluations of the hash function using a birthday attack.

However, how many evaluations are required to produce two or more collisions?

Note I am talking about distinct collisions i.e. $H(A)=H(B)$, $H(C)=H(D)$, etc.
The expected effort to find $k$ distinct collisions on an ideal hash function of output size  $n$ is about $\sqrt{2k} \cdot 2^{n/2} = \sqrt{k2^{n+1}}$ (for $k &lt;&lt; 2^{n/2}$).

One way to see this is to look at the probability of the outputs of two distinct inputs colliding, which is $2^{-n}$; if we generate outputs for $\sqrt{2k} \cdot 2^{n/2}$ distinct inputs, there are $(\sqrt{2k} \cdot 2^{n/2} \cdot (\sqrt{2k} \cdot 2^{n/2}-1))/2 \approx 2^nk $ pairs of outputs; if the collision probabilities are independent (which they approximately are if we stay $k &lt;&lt; 2^{n/2}$), then the expected number of collisions we get in the set of outputs is $2^{-n} \cdot 2^nk = k$

Note that for $k=1$, we get about $\sqrt{2}\cdot 2^{n/2}$ expected outputs for a single collision.  That's not a contradiction to the $2^{n/2}$ rule of thumb; $\sqrt{2}\cdot 2^{n/2}$ is a slightly more precise value.