02 · The bet
One-way
Multiply two primes in one step. Factoring the product is a search up to √n. That gap, at 2048 bits, is RSA. At 8 bits it is a lab.
In English
Easy forward, hard backward: multiply two primes in one multiply; recovering them from the product is a hunt. That gap, when the numbers have hundreds of digits, is the bet behind RSA. Here the numbers are tiny so you can see the hunt.
- Try this
- Pick two primes. Note n appears instantly. Count how many trial divisions recover them.
- Keep this
- One-way = cheap forward, expensive reverse — unless you know a secret.
Lab · multiply is easy
Pick two primes. Their product is instant. Recovering them is a search up to √n. That gap is RSA’s whole bet — at 2048 bits, not at 8.
Prime p
Prime q
- n = p·q
- 221
- Multiply
- 1 multiply
- Trial divide
- 7 tries → 13×17
A one-way function is cheap to compute and expensive to invert on average. Multiply is the school example. Factoring is the inverse. RSA’s private key is that inverse, cached.
At these sizes the search is a handful of trial divisions. At 2048 bits, trial division is not the algorithm anyone uses — and it is still not Shor. Shor is period-finding, Volume III.