Birthday Paradox

Updated 12 Aug 2026

•
Definition
- •
  if you draw roughly $1.2\sqrt{|U|}$ independent samples (not even necessarily uniform, just identically distributed) from a universe $U$ , there's a better-than-even chance two of the samples collide (are equal)
•
Why "paradox"
- •
  the number of samples needed is much smaller than intuition suggests — with 365 days in a year, only about 23 people are needed for a >50% chance two share a birthday, even though 23 feels small relative to 365
•
Concrete crypto example
- •
  over a universe of $2^{128}$ strings (a huge set), only around $2^{64}$ samples (the square root) are needed before a collision becomes likely — this is why hash/key lengths are often chosen with the square root of the ideal security level in mind
•
Related
- •
  Collision (Hashing)

Linked references 1