Level 8: Secret codes and open questions¶
Number theory · level 8 of 8 · rough age 17 and beyond (a guide for parents; anyone can start anywhere)
The last level puts the whole topic to work. You will see why old letter-swapping codes break, and how RSA and Diffie-Hellman use Euler's theorem and fast powers to keep messages secret even when the method is public. Then the level turns from what is known to what is not: how the primes are spread out, which famous questions are still open (and how Fermat's last theorem was finally settled), and which numbers are squares on a prime clock.
| Lesson | You will be able to |
|---|---|
| Old codes and why they break | Use Caesar and affine ciphers as arithmetic mod 26, and break them by brute force and frequency analysis |
| RSA: a lock anyone can close | Make an RSA key, encrypt and decrypt with it, and explain why it works (Euler) and why it is safe (factoring) |
| Diffie-Hellman key exchange | Agree on a shared secret in public with powers mod \(p\), and explain the discrete logarithm problem |
| How the primes are spread out | Use the prime counting function and the prime number theorem, and build prime gaps as long as you like |
| Famous open problems | State the twin prime and Goldbach conjectures and the Riemann hypothesis, and prove Fermat's last theorem for \(n = 4\) |
| Quadratic residues | Find the squares mod \(p\), prove there are \((p-1)/2\), use Euler's criterion, and show when \(-1\) is a square |
Previous: Level 7: powers on a clock · This is the last level · Number theory topic page · Further: cryptography.akadian.ca