Engineering / Mathematics — Discrete Probability
The Birthday Paradox
The birthday problem, the square-root threshold for collisions, and its algorithmic consequences.
Executive summary
Drawing uniformly from a set of size N, a repeated value appears after about the square root of N draws — far sooner than intuition suggests.
The square-root threshold is the reason hash outputs must be twice the desired security level and the reason several factoring and discrete logarithm algorithms achieve square-root running time.
Learning objectives
- Derive the collision probability and the square-root threshold.
- Apply the bound to hash output sizing.
- Recognise the algorithms that exploit it.
01The collision probability
No-collision probability
Drawing k values uniformly and independently from a set of size N, the probability that all are distinct is
∏_{i=1}^{k−1} (1 − i/N) ≤ exp(−k(k−1)/(2N)).
The bound uses 1 − x ≤ e^{−x} term by term. Setting the exponent to a constant gives k ≈ √N, so a collision becomes likely once the number of draws reaches the square root of the space size.
k ≈ 1.177√N gives collision probability 1/202Consequences for hash sizing
| Output size | Collision work | Status |
|---|---|---|
| 128 bits | 2⁶⁴ | Broken in practice |
| 160 bits | 2⁸⁰ | Deprecated |
| 256 bits | 2¹₂⁸ | Current standard |
| 512 bits | 2²⁵⁶ | Long-term margin |
Preimage resistance is a different question and costs 2^n, so the factor-of-two penalty applies specifically to collisions. Protocols that rely only on preimage resistance can safely use shorter outputs.
03Algorithms exploiting the threshold
Baby step/giant step
Computes a discrete logarithm in a group of order q using about √q operations, by seeking a collision between two constructed lists.
Pollard's rho
Achieves the same √q cost with constant memory, by detecting a cycle in a pseudorandom walk rather than storing a table.
Birthday attacks on signatures
An adversary generating many variants of two documents finds a colliding pair in about 2^{n/2} work, which is why signature schemes hash before signing with adequate output size.
The memory difference between the first two is what makes Pollard's rho the practical choice: both cost √q time, but baby step/giant step needs √q storage, which becomes the binding constraint long before the time does.
04Frequently asked questions
Why is it called a paradox?
Only in the sense of being counterintuitive; there is nothing contradictory. The intuition fails because people estimate the number of values rather than the number of pairs, and pairs grow quadratically.
Does non-uniformity make collisions more or less likely?
More likely. Uniformity maximises the expected time to a collision, so any bias in a hash function only reduces the effective security below the birthday bound.
Does the bound require mutual independence?
The clean product formula does. Pairwise independence suffices for a weaker but still square-root-order bound via the second moment, which is why pairwise independent hash families are adequate for collision-counting arguments.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 121-125.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.