Talk:Birthday paradox

Table for data

Is there an easy way to put data, like in this article, into a table? --David W Gillette 14:55, 21 July 2007 (CDT)

I've just put your data into a table - have a look at how it's constructed. Anthony Argyriou 10:58, 22 July 2007 (CDT)

Thanks, it looks great.--David W Gillette 15:45, 22 July 2007 (CDT)

Is there a mathematician in the house?

I've just added an article birthday attack on a cryptographic application of the birthday paradox, with a link from here.

Part of the text there is: "In general, for a cryptographic primitive of size n bits, the attack cost is 2^n/2." That's a well-known rule among crypto folk; it's in the standard references and is used in government standards, see the last paragraph of birthday attack. However, I've never seen a proof and do not know if it is a theorem or just a handy approximation. Can anyone clarify this? Sandy Harris 13:32, 1 November 2008 (UTC)

I don't know what a cryptographic primitive is, and the article does not explain it (hint!). But I guess it is something like a hash function. If you use n-bit hash values (each of them equally likely) and then there is a 50% chance of a hash collision if you compute the hash of about 1.18 · 2^n/2 pieces of data.

With n bits there are N = 2ⁿ possibilities, so if you take k pieces of data, the probability of a hash collision is (the same formula as in the article):

$1-{\frac {N!}{(N-k)!\cdot N^{k}}}.$

Using Stirling's approximation for the factorial and assuming that k is large and N even larger, we find the approximation

$1-{\frac {N!}{(N-k)!\cdot N^{k}}}\approx 1-\exp \left(-{\frac {k^{2}}{2N}}\right).$

Let me know if you're interested in the details of the computation. So the probability is 50% if

$\exp \left(-{\frac {k^{2}}{2N}}\right)={\tfrac {1}{2}},$

and solving this yields

$k={\sqrt {2\ln 2\cdot N}}\approx 1.18{\sqrt {N}}.$

For instance, if N = 365 (which is the case in the article) then you get k = 1.18 · N^1/2 = 22.5, which is a pretty good approximation for the size of the group you need to get two people with the same birthday. -- Jitse Niesen 00:48, 2 November 2008 (UTC)

That's all I needed. Thanks. Sandy Harris 02:56, 2 November 2008 (UTC)