Hash collisions and the birthday problem: a maths EPQ idea
A title to start from
How likely are two different files to share a hash, and what does the birthday problem say about security?
Why it works as an EPQ
The birthday problem gives a precise estimate you can test on a deliberately small hash.
Scope and difficulty
Solid. Solid. Use a truncated hash in code so collisions happen in seconds.
The maths
Builds on these A Level topics: Probability · Exponentials and logarithms.
You would learn:
- Hash functions
- Approximations using eˣ
- Square-root attacks
One possible plan
- Derive the collision probability and the √N rule of thumb.
- Truncate a hash to a few bits and count collisions.
- Compare with the theory.
- Judge what hash length is needed and why.
Pitfalls
- Confusing finding any collision with matching a given file.
- Approximations used outside their range.
Where to start reading
- Search for: birthday attack hash collision probability
- Search for: approximation 1 - x ≈ e^-x birthday problem
Similar ideas
- How RSA keeps payments secureHow does RSA encryption keep online payments secure, and what would it take to break it?
- Which sorting algorithm is fastest?Which sorting algorithm is fastest in practice, and does Big O notation tell the whole story?
- How search engines rank pagesHow can matrices and probability rank web pages, and how could the ranking be manipulated?
- How QR codes survive damageHow can a damaged QR code still be read? The mathematics of error-correcting codes
All maths and computer science ideas · all 93 ideas
Your EPQ must be your own work. These pages coach: ideas, structure, checklists and planning. Submitting text, proofs, code or analysis written by someone else or by an AI tool as your own is malpractice. How to use help and AI honestly.