Part 3 · 1 chapters · ~8 min

Counting

The sum and product rules, permutations and combinations, binomial coefficients, the pigeonhole principle, inclusion-exclusion, the birthday bound computed for ids and OTPs, password and PIN space sizes, and estimating brute-force effort.

Count before you trust randomness

code

// birthday bound: P(collision among k items in N slots) ≈ 1 - e^(-k(k-1)/2N)
const p = (k, N) => 1 - Math.exp(-k * (k - 1) / (2 * N));
p(1e5, 2 ** 32)       // 0.688  → random 32-bit ids: 68.8% collision chance at 100,000 ids
p(1e6, 2 ** 64)       // 2.71e-8
// six-digit OTPs: after about 1,178 codes, two are more likely than not to be equal
//   (harmless for OTPs, which are per-user and short-lived; fatal for ids)

C(52, 5) = 2,598,960 poker hands         // combinations: order does not matter
10^6 six-digit PINs                      // product rule: 10 choices × 6 positions
36^8 = 2,821,109,907,456 eight-char a-z0-9 passwords
// pigeonhole: 2,821 billion passwords hashed into 32-bit values must collide;
// any hash with fewer outputs than inputs has collisions, so security relies on finding them being hard

Brute force: a six-digit OTP has a million values, so an attacker allowed unlimited guesses finds it after 500,000 on average; with five attempts per code the success chance is 5 in a million. Counting is the argument for rate limits (Backend Disciplines P1).

THE BIRTHDAY BOUND, COMPUTED

probability that at least two random values collide

swipe the figure sideways, or tap expand for full screen

1/4

birthdays

With 23 people, the chance two share a birthday is 50.7%: there are 253 pairs, and each pair can collide.

23 people: 50.7%253 pairs