Why does a lock that anyone can close need a factoring problem to stay open only for you?
Public-key cryptography is what lets strangers talk safely, and it is the half a quantum computer breaks. These topics show how each lock works and what it rests on, using numbers small enough to follow, so that topic 07 can say exactly what Shor's algorithm does to them.
RSA, named for Rivest, Shamir and Adleman (described in 1977, published in 1978), is a lock with two different keys. The public key closes it, the private key opens it, and the public key can be handed to the whole world. It rests on a difference in difficulty: multiplying two large primes is a moment's work, while taking their product apart is, for classical computers, not. So the modulus n = p × q is public and the primes are the secret.
The example above is textbook RSA, deliberately tiny so you can check it by hand, and not something to use as it stands. Real RSA pads the message with random structure first (OAEP for encryption, PSS for signatures), because the bare version is deterministic and malleable. The padding is a large part of what makes it safe in practice.
Notice what the weak point is. It is not the exponentiation and not the padding. It is a single assumption: that factoring n is hard. Nobody has proved it. There is no known fast classical method, there is no proof that none exists (one of the open problems), and there is a fast quantum one. Every RSA key anywhere is a bet on that one sentence.
Key generation. Choose primes p and q, set n = pq and φ(n) = (p − 1)(q − 1). Choose e coprime to φ(n), and compute d with e·d ≡ 1 (mod φ(n)). With p = 61, q = 53:
n = 3233, φ = 60 · 52 = 3120, e = 17, d = 2753, 17 · 2753 = 46801 = 15 · 3120 + 1
Why it works. Encrypt: c = me mod n. Decrypt: cd = med = m1 + kφ ≡ m (mod n), by Euler's theorem. Here 6517 mod 3233 = 2790 and 27902753 mod 3233 = 65. For this toy, every message from 0 to 3232 survives the round trip, which is easy to check by trying all of them.
Signing is the same machine run the other way. Raise a message to d, and anyone can raise the result to e and compare: 12342753 mod 3233 = 1512, and 151217 mod 3233 = 1234.
The attack. Factor n and you can compute φ, and then d. Trial division finds 53 in at most 52 steps for the toy. A 2,048-bit modulus has 617 decimal digits, and the best classical factoring methods (the number field sieve) take sub-exponential time that leaves it at roughly 112 bits of security by NIST's reckoning. Shor's algorithm factors in polynomial time, which is the subject of topic 07.
Choose two secret primes and a message and see the whole round trip. The default is the one in the figure. Then let the attacker factor n by trial division, which works instantly here because n is tiny; that is the whole weakness of RSA, shrunk to a size you can watch.
Certificates, mostly RSA key exchange has gone from TLS 1.3, which removed it entirely. RSA signatures are still everywhere in certificate chains, code signing and email, and 2,048-bit keys are the long-standing minimum.
Why this one is the poster child Factoring is one of the two problems Shor's algorithm was built for (the discrete logarithm is the other), and the resource estimate for it has dropped more than twenty-fold in six years. A tiny RSA number is also a good first thing to try in Shor's Clockwork, which does the last classical step by hand.
Check yourself
In textbook RSA the public modulus is 3233 = 61 x 53. What can someone who knows the factors 61 and 53 do that nobody else can?
The private exponent d satisfies 17 x d = 1 mod 3120, and 3120 comes from the two factors. Anyone can encrypt with the public pair; only factoring the modulus gives you d, which is why RSA rests on factoring being hard.