ABSTRACT
The birthday paradox is a ubiquitous paradigm in cryptography. In some sense, it can be seen as an efficient probabilistic variation on the pigeonhole principle. Recall that the pigeonhole principle is a very general rule, that says that, given n disjoint classes of objects and a set of N objects, if N > n then there is at least one class containing two or more objects. In this context, we say that the two objects collide in the same class or simply that we have a collision. Using this terminology, the pigeonhole principle simply states that given n classes, with at least n + 1 objects, a collision always occurs. In a probabilistic context, assuming that objects are equiprobably distributed among classes, it is natural to ask: How many objects do we need to have a collision with probability greater than one half?
