Capstok — learn by doing

Why this matters

Every widely-deployed public-key cryptosystem in 2026 — RSA, finite-field Diffie-Hellman, elliptic-curve Diffie-Hellman, ECDSA — derives its security from one of two computational assumptions: integer factorisation is hard, or discrete logarithm in some group is hard. Shor's 1994 algorithm solves both in polynomial time on a sufficiently large fault-tolerant quantum computer. That is not a marginal improvement — it is a complete break. NIST's post-quantum standardisation program (Kyber, Dilithium, SPHINCS+, Falcon) exists because of this single fact: we need primitives whose hardness reduces to problems for which no efficient quantum algorithm is known (lattice problems, code-based problems, multivariate-polynomial problems, hash-based signatures). This task is the bridge — every concept in the previous seven tasks combines into the high-level picture of why Shor works, and therefore which cryptographic primitives we have to retire and which we have to build.

Demo

Shor's algorithm reduces factoring $N$ to finding the order $r$ of $a$ modulo $N$ — i.e. the smallest $r$ with $a^r \equiv 1 \pmod N$ . Quantum order-finding works in three stages: (1) prepare a uniform superposition of inputs $x$ and compute $a^x \bmod N$ into a second register, entangling them; (2) measure the second register, collapsing the first into a periodic superposition over $\{x_0, x_0 + r, x_0 + 2r, \ldots\}$ ; (3) apply the quantum Fourier transform, whose interference pattern concentrates amplitude on multiples of $2^n / r$ . Classical post-processing recovers $r$ , and from $r$ a non-trivial factor of $N$ .

\text{Order finding: find } r \text{ s.t. } a^r \equiv 1 \!\!\!\pmod N, \quad \text{then } \gcd(a^{r/2} - 1,\, N) \text{ is (often) a non-trivial factor of } N

Try it yourself

Run the snippet and verify $15 = 3 \times 5$ is recovered via order-finding. Try $a = 11$ instead. What's $r$ ? Does the trick still factor $N$ ?
Replace $N = 15$ with and try a few small coprime to . Find an for which is even and — those are the cases where the trick succeeds. Estimate empirically what fraction of valid 's work.

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain why factoring is the basis of RSA security. Then explain in one paragraph why Shor's algorithm changes the picture: what does it solve in polynomial time that no classical algorithm can?

2. Why it works (the mechanism)

Walk me through Shor's algorithm at a high level: (1) reduction from factoring to order-finding, (2) why the quantum Fourier transform extracts the period, (3) the role of continued fractions in classical post-processing. Where is interference doing the work?

3. Advanced — application & what's next

Of the four NIST PQC selections (Kyber, Dilithium, Falcon, SPHINCS+), each rests on a different hardness assumption. Compare lattice-based (LWE, Module-LWE) versus hash-based (SPHINCS+) approaches: what are the assumptions, what's the parameter cost, and why are *both* in the standard rather than picking one winner?

References

// main.go
package main

import (
	"fmt"
	"math/big"
)

// classicalOrder finds the smallest r such that a^r ≡ 1 (mod N).
// Brute force - exponential in log N classically.
func classicalOrder(a, N int) (int, bool) {
	r := 1
	for modPow(a, r, N) != 1 {
		r++
		if r > N {
			return 0, false
		}
	}
	return r, true
}

// modPow computes base^exp mod m using big.Int for correctness.
func modPow(base, exp, mod int) int {
	b := big.NewInt(int64(base))
	e := big.NewInt(int64(exp))
	m := big.NewInt(int64(mod))
	result := new(big.Int).Exp(b, e, m)
	return int(result.Int64())
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func main() {
	N := 15 // the canonical Shor toy instance
	a := 7  // coprime to 15
	r, ok := classicalOrder(a, N)
	if !ok {
		fmt.Println("order not found")
		return
	}
	fmt.Printf("order of %d mod %d is r = %d\n", a, N, r)
	if r%2 != 0 {
		panic("need even r for the trick")
	}
	x := modPow(a, r/2, N)
	fmt.Printf("a^(r/2) mod N = %d\n", x)
	factor1 := gcd(x-1, N)
	factor2 := gcd(x+1, N)
	fmt.Printf("gcd(x-1, N) = %d\n", factor1)
	fmt.Printf("gcd(x+1, N) = %d\n", factor2)
	fmt.Printf("so %d = %d * %d\n", N, factor1, factor2)
	// This is what the QFT-based quantum subroutine accelerates: it finds r in
	// polynomial time in log N rather than exponential time.
}

Run: go run main.go

Why quantum computers break public-key cryptography (overview)