Birthday attack

[John R T Brazier]

Graham quoted:

> [snip]
>(N2 * 1/K) / 2 = 0,5
> N = sqrt(K) = 264.

... approximately.

As K tends to infinity, the number you would expect to generate before
getting a match becomes squareroot(Pi*K/2). This is actually a good estimate
even when K is relatively low. So for K = 365 (the birth days)
squareroot(Pi*364/2) = 23.94 - not a bad estimate. If we imagine a 6-bit
hash (64 possibilities), then squareroot(Pi*64/2) = 10.03, which is almost
spot on (you need 10 samples to be over the 0.5% probability).

TTFN

John B