IB Maths IA idea · Crypto and cryptography

The birthday problem: how safe are hash codes?

In a room of just 23 people, the chance that two share a birthday is already about one half. The same arithmetic decides how long a digital fingerprint must be. Your job is to explain why the number is so small and then use it.

Crypto and cryptography
SL ideal
HL ideal
Maths AA Maths AI Mixed data
Syllabus: AA 1.7, AA 2.9, AA 4.5, AA 5.19

By Photon Academy · Updated 13 November 2026

These ideas are starting points, not an IA to copy. Never copy an idea blindly: make the question, method and analysis your own, and check your plan with your teacher.

The big idea

The chance that n people all have different birthdays is a product: 365/365 × 364/365 × 363/365 and so on. Subtract it from 1 for the chance of a match. That is exact but awkward. Replace each factor 1 − i/N by $e^{-i/N}$ , which comes from the first term of the Maclaurin series for ln(1 − x), and the product collapses to $e^{-n(n-1)/2N}$ . Test how good that is, not just whether it looks right. Now let N be the number of possible values of a hash code, which is $2^{b}$ for a b-bit code. A clash is likely after about √N items, so the code gives only about b/2 bits of protection against collisions. Real birthdays are not evenly spread, which changes the answer. Decide what to include and defend it.

The maths you will use

Probability of the complement. Write the chance of no match as $\prod_{i=0}^{n-1}(1-i/N)$ and subtract from 1; check small cases by listing outcomes.
Logarithms and series. Take $\ln$ of the product, use $\ln(1-x)\approx -x$ from the Maclaurin series, and sum an arithmetic series.
Exponential equations. Solve $e^{-n(n-1)/2N}=\tfrac12$ for $n$ to get about $1.18\sqrt{N}$ .
Approximation error. Compute the relative error against exact values and compare one-term and two-term series.
Simulation. Simulate random groups to estimate probabilities and give a margin of error for them.

Key equations

P(\text{no match}) = \prod_{i=0}^{n-1}\left(1-\frac{i}{N}\right) \approx e^{-n(n-1)/2N}

n_{1/2} \approx \sqrt{2\ln 2\, N} \approx 1.18\sqrt{N}

The maths in action

Two panels. Left: two almost identical rising curves of match probability against group size, with the 50% point at 23 people marked. Right: the relative error of the approximation, a shallow dip for one term and almost zero for two terms. — (a) The exact chance of a shared birthday and its exponential approximation for N = 365: at n = 23 they are 50.7% and 50.0%. (b) The one-term approximation is at most 1.5% too small; adding a second Maclaurin term nearly removes the error.

Example research question

To adapt, never to copy

For N equally likely values, how closely does the Maclaurin approximation 1 − $e^{-n(n-1)/2N}$ follow the exact probability of a shared value, and what does it imply for the number of inputs at which a b-bit hash is likely to collide?

Change the context, the data or the method so the question is yours. Our Maths IA guide shows how to check it.

Check your research question

Names the model: the number of possible values N and the assumption that they are equally likely, or a stated alternative.
Names the quantity you find: a probability, the size of group for a given chance, or the bits of protection.
Says how the approximation is tested: exact values, simulation or real data.
Includes a step that is justified, not just calculated: the series, the error or the solved equation.
States what you leave out: leap days, twins, seasonal birth patterns and the way real hash functions are attacked.

Which course it fits

AA SL good
AA HL ideal
AI SL ideal
AI HL ideal

Syllabus links in Maths AA:

AA 1.7 Rational exponents and laws of logarithms
AA 2.9 Exponential and logarithmic functions
AA 4.5 Basic probability and expected frequency
AA 5.19 Maclaurin series (HL only)

Steps

Read and predict. Before any calculation, guess how many people give a 50% chance of a shared birthday. Write the guess down.
Set up the model. State your assumptions: 365 equally likely days, independent birthdays. Define the event 'no two share' and write its probability as a product.
Check small cases. Compute n = 2 and n = 3 by listing outcomes, and compare with your product. Fix any slip now.
Trial run (1 lesson). Build a table of exact probabilities for n = 1 to 60 in a spreadsheet or program, and find where it first passes one half.
Derive the approximation. Take logs, use the Maclaurin series of ln(1 − x) and sum the resulting series. Write the formula and show the steps.
Measure the error. Compare exact and approximate values over a range of n. Find the largest relative error and say where it is.
Move to hash codes. Put N = $2^{b}$ in your formula and find the number of items for a 50% chance. Compare with simulated collisions on a small b.
Go further, with a reason. Test unequal probabilities with real data, or go to three-way matches. HL: use a second series term and bound the error.
Reflect as you go. After every result, write one line on what it means and what it assumes. These lines become your evaluation.
Cut, check, then send. Check every graph has labelled axes, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.

Make it yours

Derive the approximation. Take logs of the product, replace each ln(1 − i/N) by its Maclaurin series, and sum the first one or two terms.
Find the 50% point. Solve $e^{-n²/2N}$ = ½ for n and compare with exact values for several N.
Size a hash code. For a b-bit hash, find how many items give a 50% and a 1-in-a-million chance of some collision.
Uneven birthdays. Use real birth statistics for a country and compute the chance of a match with unequal probabilities.
Simulate it. Draw many random groups, estimate the match probability and compare it with your formulas.
Three people, not two. Find how large a group must be for three people to share a birthday.

HL extension

Prove the bounds $e^{-x-x^2}\le 1-x\le e^{-x}$ on a suitable range, use them to bound the error of the approximation for all $n$ , and compare with the unequal-probability case.

The data you need

Exact calculation and simulation, with national birth statistics (births per day of the year) to test the equal-chance assumption.

Traps

Calculating the chance that someone shares your birthday. That is a different and much smaller probability.
Writing the approximation without saying where it comes from or how large its error is.
Using n² instead of n(n − 1), and then not noticing a small difference for small n.
Treating 'a collision is likely' as meaning 'a given hash can be attacked'. The attacker also has to choose the inputs.
Leaving out the equal-chance assumption, or claiming real birthdays satisfy it without checking.
Reporting a simulation result with no number of trials and no margin of error.

More Maths IA ideas in Crypto and cryptography

Bitcoin's 21 million cap: a geometric series in codeFree with an account
Every four years or so, the reward for adding a block to Bitcoin's chain is cut in half. That sounds like it should never end, yet the total can never pass 21 million. Your job is to explain why an endless process has a finite total.
Swapping crypto without a market: the constant-product ruleFree with an account
Some exchanges have no buyers and sellers at all. A pool holds two kinds of token, and one rule sets every price: the amounts multiplied together never change. You will find out what that rule does to the price you get.
How many confirmations are safe? The double-spend raceIn the Photon IA Guide
A shop sees your payment but waits for a few more blocks before handing over the goods. Wait for too few and a cheat with enough computing power can reverse it. Wait for too many and nobody buys anything. You are going to find the number that balances the two.
Elliptic curves: the maths inside a crypto walletIn the Photon IA Guide
Take two points on a curve, draw a line, find where it hits the curve again and flip it. That strange recipe is a way to add points, and it is the basis of the keys in many crypto wallets. You will check why the recipe never leaves the curve.
RSA: why can nobody read your messages?In the Photon IA Guide
You can publish a number on the open internet that lets anyone lock a message to you, and still be the only person who can unlock it. Why can't they just work it out?