Paradoxo do Aniversário

The birthday paradox

Take a group of n people. The chance that at least two of them share a birthday works out to P(n) = 1 − 365! / ((365−n)! · 365^n). At n = 23 you already cross 50%: P ≈ 50.7%, so a match is slightly more likely than not. Push it to n = 70 and P ≈ 99.9%. Most people find this hard to believe because they picture a number somewhere near 365. The trick is that you're counting pairs rather than individuals, and a group of 23 holds C(23,2) = 253 of them. That's why the probability climbs quadratically with n.

Applications

In cryptography, the birthday attack locates collisions in a k-bit hash function after roughly 2^(k/2) trials rather than 2^k. SHA-256 sits at a 2^128 birthday bound and remains unbreakable, while MD5 (2^64) and SHA-1 (2^80) are both considered broken. The same math shows up elsewhere: spotting duplicates in a dataset, reasoning about whether GUIDs/UUIDs will stay unique, balls-and-bins problems, sizing a hash table, and statistical sampling.

FAQ

Why does P(23) ≈ 50% surprise people? Our gut latches onto "my birthday" and the 1-in-365 odds attached to it. But the question being asked is about any two people in the room, and the count of pairs scales with n², not n.

Does it consider leap years? No. The standard formula treats all 365 days as equally likely. Add a 366th day and the curve nudges a little. Actual birth distributions aren't uniform either, but at n=23 the difference barely registers.

What's a birthday attack? It's a collision attack on hashes. Rather than brute-forcing one specific preimage, you hunt for any two inputs that hash to the same output. That search succeeds in about 2^(k/2) tries, which effectively cuts the security in half.