How to compute the birthday paradox with n people

Compute birthday paradox probability n people sharing same birthday. Exact formula P=1-prod((365-i)/365). Approximation exp(-n(n-1)/(2*365)). n=23 50.73%, n=50 97%, n=70 99.9%. Birthday attack hash MD5 SHA-1 cryptography.

Calculation parameters
Was this calculator useful?

How to compute the birthday paradox: counterintuitive probability that in a group of n people at least two share the same day-month of birth. Exact formula: P(collision) = 1 - prod_{i=0}^{n-1}((365-i)/365), cumulative product complement no collision probability. Effective exponential approximation: P ≈ 1 - exp(-n(n-1)/(2*365)). Surprising result: with only n=23 people P=50.73% at least two same birthday (intuitive expectation 365/2=182 wrong), n=50 P=97%, n=70 P=99.9%, n=100 nearly certain P=99.99996%. Generalization: space N possible states, n independent uniform samples, P_collision ≈ 1 - exp(-n²/(2N)); 50% collision requires n ≈ sqrt(2N*ln(2)) ≈ 1.177*sqrt(N). History: Richard von Mises (Austria-USA 1883-1953) Wahrscheinlichkeitsrechnung 1939, Harold Davenport England 1927 prior informal observation, Persi Diaconis Stanford 1977, Donald Knuth (USA 1938-) Stanford 'The Art of Computer Programming' Volume 3 Sorting Searching 1968+ hashing cryptography birthday attack application.

Essential tool for: cryptography information security (FIPS 180-4 NIST Boulder CO USA SHA-256 hash 2^128 collision resistance, MD5 broken 2008 birthday attack 2^64 operations Wang Yu Tsinghua 2004 collision found minutes, SHA-1 deprecated 2017 NIST collision Stevens Marc Cryptanalysis CWI Amsterdam Netherlands), applied probability teaching universities Princeton MIT Caltech Stanford Berkeley Cornell Carnegie Mellon Pittsburgh PA, USA lottery Powerball Mega Millions National Association of State Lotteries; data analytics Big Data hash collision Database PostgreSQL MySQL Oracle USA Redmond WA cloud Azure AWS; insurance statistics actuarial life expectancy SOA Society Actuaries Schaumburg IL.

Birthday paradox formulas

Exact non-collision probability formula: P(no collision) = (365/365) * (364/365) * (363/365) * ... * ((365-n+1)/365) = 365! / (365^n * (365-n)!). Collision probability = 1 - P(no collision). Iterative calculation to avoid numerical overflow: prod_{i=0}^{n-1}((365-i)/365). Validity: n ≤ 365 (beyond P=1 certainty pigeonhole principle). Leap year 366: marginal accuracy increase 0.27%.

Taylor exponential approximation: for n small relative to 365, ln(1-x) ≈ -x. P(no collision) ≈ exp(-n(n-1)/(2*365)). P(collision) ≈ 1 - exp(-n(n-1)/(2*365)). Approximation error < 0.01% for n ≤ 50; error grows n=100 up to 0.3%. Advantage: closed form O(1) calculation vs O(n) iterative, useful cryptography large N analysis.

Generalized birthday problem: space N possible values (days, hash bits, IDs etc), n independent uniform samples. P_collision ≈ 1 - exp(-n²/(2N)). Required n for target probability p: n ≈ sqrt(-2N*ln(1-p)). For p=50%: n ≈ sqrt(2N*ln(2)) ≈ 1.177*sqrt(N). For p=99%: n ≈ sqrt(2N*ln(100)) ≈ 3.034*sqrt(N).

Possible pairs count (paradox explanation): with n people, distinct pairs = C(n,2) = n(n-1)/2. For n=23: pairs=253. Each pair probability 1/365 same birthday (assuming uniform). P(at least one collision) approximately pairs/365 = 253/365 = 69% upper bound (ignores overlap). Exact Poisson approximation 1-exp(-253/365) = 50.4%, accurate.

Birthday attack cryptography: hash function H output b bits, space N=2^b. Brute force find two inputs m1,m2 with H(m1)=H(m2): collision attack cost 2^(b/2) operations (NOT 2^b like preimage). MD5 b=128, collision 2^64 = 1.8e19 operations, feasible GPU cluster; SHA-1 b=160, collision 2^80 = 1.2e24, demonstrated 2017 Stevens CWI; SHA-256 b=256, collision 2^128 = 3.4e38, secure post-quantum era; SHA3-256 Keccak NIST 2015 alternative.

History and context

Richard Edler von Mises (Austria-USA 1883-1953) Vienna Berlin Istanbul Boston Harvard mathematician philosopher probability frequentist formalization 1928 "Wahrscheinlichkeit, Statistik und Wahrheit" introduced birthday paradox didactic problem 1939 lectures University Berlin emigrated USA fascism. Harold Davenport (England 1907-1969) Cambridge mathematician earlier 1927 informal observation. George Polya (Hungary-USA 1887-1985) Stanford 1965 "Mathematical Discovery" classic probability book. Persi Diaconis (USA 1945-) Stanford ex-magician transition mathematician 1977 advanced probabilistic analysis. Donald Knuth (USA 1938-) Stanford "The Art of Computer Programming" Volume 3 Sorting Searching 1973 first edition hashing collision Birthday paradox application; Volume 4A Combinatorial Algorithms; Volume 4B 2025 published. Hash function history: Ronald Rivest (USA 1947-) MIT Cambridge MA RSA cryptosystem 1977, MD5 1991 RFC 1321 widely deployed banks USA JPMorgan Chase Bank of America Wells Fargo Internet Banking pre-2010 replaced SHA-256 post-collision discovery 2008. SHA-0 NIST 1993 retired 1995 weakness, SHA-1 1995 RFC 3174 Microsoft Apple Google deployed 2000s SSL certificates HTTPS, deprecated 2017 collision Stevens Marc CWI Amsterdam Netherlands SHAttered.io Google CWI demonstration two PDF different same hash SHA-1, $110000 GPU cloud Amazon AWS. SHA-2 family SHA-256 SHA-512 NIST FIPS 180-2 2002 standard worldwide HTTPS TLS Bitcoin blockchain mining reward.

SHA-3 Keccak Belgian competition NIST 2007-2012 winner Keccak Joan Daemen Vincent Rijmen STMicroelectronics Geneva alternative permutation-based. USA cryptography research: NIST National Institute Standards Technology Boulder CO Gaithersburg MD federal precision time standards cryptography modules CMVP Cryptographic Module Validation Program; CMU CyLab Carnegie Mellon Pittsburgh PA cybersecurity research center; UC Berkeley CA, MIT Cambridge MA Computer Science AI Lab, Stanford Computer Science Department Cryptography Group, Princeton NJ; Caltech Pasadena CA. NSA National Security Agency Fort Meade MD signal intelligence cryptanalysis. USA federal cybersecurity: CISA Cybersecurity Infrastructure Security Agency Washington DC founded 2018 DHS Department Homeland Security; FBI Federal Bureau Investigation Quantico VA cyber crimes division. Universities probability statistics USA: Princeton NJ Statistics, MIT Cambridge MA, Stanford CA Statistics PhD ranked #1, UC Berkeley CA, Cornell Ithaca NY, Carnegie Mellon Pittsburgh PA Statistics Data Science. Cryptographic applications USA: federal services hash SHA-256 standard PIV Personal Identity Verification cards FIPS 201; SSL certificates HTTPS Let s Encrypt ISRG Internet Security Research Group San Francisco CA non-profit free 200 mln domains; Bitcoin blockchain mining 2009 Satoshi Nakamoto pseudonym SHA-256 proof-of-work; HTTPS TLS 1.3 RFC 8446 mandatory SHA-256+ deprecated MD5 SHA-1 2017+.

Powerball Mega Millions USA lotteries hash collision rare combinations jackpot duplicate analysis state lotteries Multi-State Lottery Association MUSL. UEFA Champions League European football 32 teams group stage seeding draws collisions birthdays. Insurance USA security: SOA Society Actuaries Schaumburg IL probability gemelli birthday premium calculation; ASB Actuarial Standards Board Washington DC. NLB National Library Medicine Bethesda MD bioinformatics DNA sequence collision birthday-style analysis.

Probability table vs n people

  • n=2: P=0.27% same birthday probability
  • n=5: P=2.71% (1 in 37)
  • n=10: P=11.69% (1 in 9)
  • n=15: P=25.29% (1 in 4)
  • n=20: P=41.14% (almost 50%)
  • n=22: P=47.57%
  • n=23: P=50.73% (famous "paradox" threshold)
  • n=25: P=56.87%
  • n=30: P=70.63%
  • n=40: P=89.12%
  • n=50: P=97.04%
  • n=57: P=99.01% (99% threshold)
  • n=70: P=99.92%
  • n=100: P=99.99996%
  • n=183: P nearly 100% per pigeonhole half-day
  • n=253: 50% probability one person shares birthday with specific date
  • n=366: P=1 certainty pigeonhole principle 366 more than 365
  • Distinct pairs n=23: C(23,2)=253 pairs
  • Distinct pairs n=50: C(50,2)=1225 pairs
  • Hash MD5 b=128 collision: 2^64 = 1.8 * 10^19 operations
  • Hash SHA-1 b=160 collision: 2^80 = 1.2 * 10^24 (broken 2017)
  • Hash SHA-256 b=256 collision: 2^128 = 3.4 * 10^38 (secure)
  • UUID v4 random 122 bits: 50% collision after 2.7 * 10^18 IDs
  • Bitcoin private key 2^256: brute force 2^128 hash birthday attack
  • NTLM password hash: 2^64 collision rainbow tables
  • Bcrypt cost 12: hash 4096 rounds slow brute force

Detailed numerical examples

Example 1 - Classroom n=23 students. School classroom 23 students USA high school. n=23, days=365. Calculation: P(no collision) = 0.4927. P(collision) = 50.73%. Approximation: 1 - exp(-23*22/730) = 50.02% (error 0.71%). Distinct pairs C(23,2)=253. USA: average classroom 25-30 students, P increases 56-70%; teachers can verify empirically with student birthdays.

Example 2 - Office party n=50. Corporate event 50 colleagues JPMorgan Chase NY. n=50, days=365. P(collision) = 97.04%. Almost certain shared birthday. Pairs C(50,2)=1225. USA: medium-large companies HR celebrate employee birthdays, frequent coincidences. Approximation exp: 96.51% (error 0.53%).

Example 3 - Sports team n=30. NFL roster 53 active players, MLB 26 active. NBA 15-17 active + reserves. NFL Atlanta Falcons New Orleans Saints Dallas Cowboys: n=30 staff+players. P(collision) = 70.63%. Pairs C(30,2)=435. NFL 32 teams * 53 players = 1696 total, multiple birthday collisions common.

Example 4 - Birthday attack MD5 hash collision. MD5 hash output 128 bits, space N=2^128 = 3.4 * 10^38. Calculation collision: n ≈ sqrt(2*N*ln(2)) = 2.17 * 10^19 = 2^64. Time: 1 GHz CPU evaluating 10^9 hash/s, 2^64 = 1.8e19 operations / 10^9 = 1.8e10 seconds = 570 years. GPU cluster 10000 GPUs * 10^11 hash/s/GPU = 10^15 hash/s, time 1.8e19 / 10^15 = 1.8e4 seconds = 5 hours. USA: NIST FIPS 180-4 SHA-256 standard secure NOT MD5 deprecated.

Example 5 - UEFA Champions League 32 teams group stage. UEFA Champions League 32 teams group stage USA participation MLS Major League Soccer Atlanta United DC United LA Galaxy. 32 teams * 23 starters = 736 players. n=736, days=365. n>365 pigeonhole P=1 certainty multiple collisions. Pairs C(736,2)=270480. Expected collisions: 270480/365 = 740 pairs shared birthday average. Verification statistical NFL MLB MLS sports teams empirically detected birthday coincidences.

Limits and considerations

  1. Uniform distribution assumption: real births not perfectly uniform (peaks September-October 9 months after Christmas-New Year pregnancies, valleys February); deviation up to 5% increases P(collision).
  2. Leap year February 29: treated as 366 days or ignored (0.27% effect negligible).
  3. Identical twins: same birthday automatic, excludes independence required formula.
  4. Country-specific patterns: USA seasonal birth pattern differs Italy China Brazil cultural religious factors.
  5. Generalized N small n large: exponential approximation fails, use exact formula or Stirling N!/(N-n)!.
  6. Pigeonhole principle: n > N implies P=1 certainty at least one collision; for N=365 boundary n=366.
  7. Cryptographic context: birthday attack requires randomized hash function output; NOT applicable preimage attack (cost 2^N different).
  8. Attacker memory complexity: birthday attack O(sqrt(N)) memory + O(sqrt(N)) time, rainbow table preimage trade-off alternative.
  9. Real-world distributions clustering: birthday clustering effect increases P collision vs theoretical uniform.
  10. Numerical precision: large n cumulative product underflow float64; use logarithms sum log(p) or BigDecimal arbitrary precision.

Common errors

  1. Confusing "at least 2 same birthday" with "someone specific same birthday": first n=23 50%, second n=253 50%.
  2. Using 365/2=182 intuitive wrong: ignores possible pairs quadratic growth n(n-1)/2.
  3. Neglecting pigeonhole principle n>365: P=1 always, product formula gives 0 correct.
  4. Exponential approximation small n: error irrelevant <1% generally, accumulates complex calculations.
  5. Confusing "birthday attack" with "preimage attack" cryptography: complexity different 2^(b/2) vs 2^b.
  6. Numerical product small calculation: float64 underflow large n, use log-sum.
  7. Neglecting non-uniform real birth distribution: 5% bias increases P.
  8. Pretending paradox applies twins: violates statistical independence.
  9. Confusing "common year" 365 vs "leap year" 366: 0.27% difference negligible.
  10. Generalizing birthday formula to NON-uniform problems: Poisson distribution preferred.

Numbered applications

  1. Cryptographic hash function: SHA-256 NIST FIPS 180-4 Boulder CO USA worldwide standard HTTPS TLS Bitcoin blockchain mining 2^128 collision resistance secure post-quantum.
  2. USA federal cybersecurity: CISA Cybersecurity Infrastructure Security Agency Washington DC, NSA Fort Meade MD signals intelligence, FBI Quantico VA cyber crimes.
  3. HTTPS TLS infrastructure: Let s Encrypt ISRG San Francisco CA free certificates 200 mln domains, IETF RFC 8446 TLS 1.3 mandatory SHA-256+.
  4. Bitcoin blockchain: Satoshi Nakamoto 2009 SHA-256 proof-of-work mining reward 6.25 BTC per block 2024, cryptocurrency exchanges Coinbase Binance.
  5. USA banks security: JPMorgan Chase NY Bank of America Charlotte NC Wells Fargo SF Citibank NY Goldman Sachs NY HSM Hardware Security Modules Thales Gemalto.
  6. Statistics universities USA: Princeton NJ, MIT Cambridge MA, Stanford CA #1 ranked, UC Berkeley CA, Cornell Ithaca NY, Carnegie Mellon Pittsburgh PA Data Science.
  7. Powerball Mega Millions lotteries: Multi-State Lottery Association MUSL hash collision rare jackpot combinations, NMLA National Conference State Lotteries.
  8. Insurance actuarial: SOA Society Actuaries Schaumburg IL probability calculations, ASB Actuarial Standards Board Washington DC.
  9. Sports analytics USA: NFL National Football League Atlanta GA, MLB MLS NCAA NBA NHL teams 30+ rosters birthday statistics.
  10. Bioinformatics DNA: NLM National Library Medicine Bethesda MD sequence collision birthday-style analysis genomics.

For support

For technical questions: info@calcoi.com. Educational applied probability tool. References: von Mises R 1939 'Wahrscheinlichkeitsrechnung', Knuth DE 1973 'The Art of Computer Programming' Volume 3 Sorting Searching, Diaconis P 1977 Stanford probabilistic analysis, NIST FIPS 180-4 SHA-256 SHA-512 hash functions, RFC 1321 MD5 deprecated, Stevens M 2017 SHAttered.io SHA-1 collision CWI Amsterdam.

Updated July 2026

Frequently Asked Questions

What is the birthday paradox?

Counterintuitive probability: group of n people at least two same birthday. Formula: P=1 - prod((365-i)/365) i=0..n-1. Approximation P=1-exp(-n(n-1)/(2*365)). For n=23 P=50.73% (intuitive expectation 365/2=182 wrong). Quadratic growth pairs C(n,2)=n(n-1)/2 explains paradox. History: Richard von Mises 1939 Wahrscheinlichkeitsrechnung Berlin University. Applications: cryptography birthday attack hash MD5 SHA-1 SHA-256, statistics universities Princeton MIT Caltech Stanford Berkeley Cornell Carnegie Mellon Pittsburgh PA.

How many people for 50% probability?

For 50% probability at least two same birthday need n=23 people exactly: P=50.73%. Generalization space N possible: n=sqrt(2N*ln(2))=1.177*sqrt(N). For N=365 days n=23. For N=2^128 (MD5 hash) n=2^64=1.8*10^19. For N=10000 n=118. Practical thresholds: 99% requires n=57, 99.9% n=70, 99.99996% n=100. USA: high school classroom 25-30 students P 57-70%, paradox frequently verified empirically by teachers.

How does birthday attack work in cryptography?

Birthday attack hash function H output b bits space N=2^b. Brute force find m1,m2 with H(m1)=H(m2): collision attack cost 2^(b/2) operations (NOT 2^b like preimage). MD5 b=128 collision 2^64=1.8e19 feasible GPU cluster 5 hours. SHA-1 b=160 collision 2^80=1.2e24 demonstrated 2017 Stevens Cryptanalysis CWI Amsterdam SHAttered.io Google CWI two PDF same hash $110000 Amazon AWS GPU. SHA-256 b=256 collision 2^128=3.4e38 secure post-quantum era.

Why counterintuitive result?

Common mistake: expect 365/2=182 people for 50% probability. Error ignores possible pairs quadratic growth: with n people, distinct pairs = C(n,2) = n(n-1)/2. For n=23 pairs=253 (NOT 23!), each pair 1/365 collision independent. Approximation 253/365=69% upper bound, exact calculation Poisson 1-exp(-253/365)=50.4%. Confusing 'at least 2 same' with 'specific same' (latter requires n=253 50%). Pairs quadratic growth O(n²) vs linear O(n) intuitive.

How to handle exponential approximation?

Approximation P=1-exp(-n(n-1)/(2*365)) Taylor expansion ln(1-x)=-x. Error <0.01% n<=50, up to 0.3% n=100. Advantage closed form O(1) vs O(n) iterative, useful cryptography large N analysis (hash space 2^128). For small n: P=n(n-1)/(2*365) further linear approximation. Exact preferred when precision critical (security), approximation when speed needed (large N). JavaScript Math.exp robust, BigDecimal Java Python decimal arbitrary precision for extreme cases.

What is pigeonhole principle birthdays?

Pigeonhole principle Dirichlet 1834: if n pigeons in m holes with n>m, at least one hole contains 2+ pigeons. Applied birthdays: n=366 people in 365 days implies P(collision)=1 certainty. Strong form: distribution frequencies pairs minimum 2 in n/m holes. Boundary case n=366: exact formula produces 0 (product includes term (0/365)=0), implies P=1. Algorithm should handle pigeonhole as early-return P=1 without product calculation.

How to calculate hash function security?

Hash function H output b bits security depends attacks: (1) Preimage: given hash h, find input m with H(m)=h, cost 2^b operations brute force. (2) Second preimage: given m1, find m2!=m1 with H(m1)=H(m2), cost 2^b. (3) Collision birthday attack: find two m1,m2 with H(m1)=H(m2), cost 2^(b/2) birthday paradox. SHA-256 b=256: preimage 2^256, collision 2^128, secure. MD5 b=128: collision 2^64 broken. NIST FIPS 180-4 recommends SHA-256 minimum modern security.

Comments (0)

No comments yet. Be the first!