03 · The bet

Discrete log

gˣ mod p is cheap. Recovering x is a hunt. Diffie–Hellman is that hunt as a handshake. Shor does not hunt — it finds a period.

In English

Raising g to the power x on the clock is easy (square and multiply). Given only the result, finding x is a hunt: try x = 1, 2, 3… Diffie–Hellman uses that hunt as a handshake so two people can share a secret in public. Shor does not hunt; it finds a period.

Try this: Set a secret x. Hit Hunt x and watch the brute force. That slog, at real sizes, is the security.
Keep this: Discrete log: gˣ is easy, x is not. Diffie–Hellman is that fact as a handshake.

Lab · gˣ is easy, x is not

Group of size 22, generator g=5. Set the secret x. Forward: square-and-multiply. Reverse: try x = 1, 2, 3… until gˣ matches.

Secret x = 11

y = 5^11 mod 23 = 22

Brute force · trying x = 1 · 5^1 ≡ 5

The discrete log in a multiplicative group: given g and gˣ, find x. Square-and-multiply computes the forward map in log(x) multiplies. The hunt is linear in the group order.

Diffie–Hellman: Alice’s a, Bob’s b, public gᵃ and gᵇ, shared gᵃᵇ. Elliptic curves are the same sentence in a different group. Shor’s algorithm is the same sentence too.