A Birthday Paradox Extravaganza

Breno de Medeiros

Florida State University

Fall 2005

Doing all the details of a math problem in class is fairly time-consuming, but I would like to post these details for the math inclined. Summarizing what is included here:

1. The mathematical computations that show the birthday paradox. In more precise terms, when the number of elements is sqrt(total possibilities), you expect a collision approximately 63% of the time. (People usually say, ``better than 50%'' instead of the more precise 63%, as I did in class).

2. I show that, for the case of ``bad message hashes'' colliding with ``good message hashes'' we need to compute 2 sqrt(total number of hashes), i.e., we need to create two tables, one of ``good message hashes'' and one of ``bad message hashes'', each of which has size $\sqrt{\mbox{(total number of hashes)}}$, in order to have a collision with 63% probability. This is the statement I made in class but did not have time to give a formal proof.

I start with a review of the Birthday problem, and then tackle the hash table problems.