Six notebooks for understanding the Number Theoretic Transform
The Number Theoretic Transform is one of those topics that everyone in lattice cryptography needs to understand and almost no resource teaches in the form actually used in practice. The textbooks teach the clean FFT-style NTT over an arbitrary cyclotomic ring, with cooperative moduli and friendly twiddle factors. Kyber uses a negacyclic, modulus-3329 NTT with a not-quite-clean base multiplication step, because the prime q doesn't support a full primitive 256th root of unity and they had to compromise. Every paper hand-waves over this. Every implementation has a clever Barrett-reduction macro that hides what's actually happening.
NTT-learning is the course I wanted to read when I was first wading through Kyber's reference C and trying to figure out why exactly the schoolbook NTT I'd implemented didn't match.
The structure is deliberately backward-designed. One supported route through the material:
START_HERE.ipynb— sets context, tests the environment.COURSE_BLUEPRINT.ipynb— declares the goal: by the end of this, you can read the Kyber reference and not flinch.- Six bundles, each in Lecture → Lab → Problems → Studio order:
- 01_convolution_to_toy_ntt — start with polynomial convolution, build up to a tiny NTT. - 02_negative_wrapped_ntt — the negacyclic twist, why the wrap is minus. - 03_fast_forward_ct — Cooley-Tukey butterfly schedules, bit-reversal, all of it. - 04_fast_inverse_gs — Gentleman-Sande butterflies, why the inverse looks different. - 05_kyber_ntt_and_base_multiplication — the actual Kyber NTT, q=3329, k=256, with its half-size base multiplication. - 06_debugging_ntt_failures — when your NTT is wrong, what does the error look like in the coefficients, and how do you triangulate.
COURSE_COMPLETE.ipynb— assessment, with widget-based checkpoints.
Each bundle's four notebooks aren't interchangeable. Lecture is reading. Lab is implementing. Problems is "you broke it, find the bug." Studio is "now do something the lecture didn't tell you how to do." That cadence is the entire pedagogical claim — it gets repeated six times and on the seventh repetition you've internalized it.
The course is local-first because Kyber is local: there's no API to call, the math is in your CPU, the failure modes happen in your terminal. The notebooks include a "debugging fingerprints" library — a small set of intermediate values you can print at known offsets to triangulate whether your forward NTT is wrong, your inverse is wrong, your modular reduction is wrong, or all three.
I built this because I needed it. Every time I have to read a new lattice paper, the same gap reopens. This is the resource that closes it.
What becomes possible: you read the Kyber reference implementation in C and recognize every step.