NTT Education-First Research Repo

How to write fast Number Theoretic Transform kernels — from math to metal.

Start with the notebooks in order: they walk from DFT→NTT foundations through CKKS-RNS motivation, reference implementations of Cooley-Tukey and Stockham, modular arithmetic tricks (Barrett/Montgomery/Shoup), Harvey's lazy-reduction butterflies, and finally benchmarking methodology with roofline analysis.

The Python reference package ntt_edu under src/ is the single source of truth for correctness; every optimized kernel (C++ scalar, SIMD, GPU, Tenstorrent) is validated against it.

Setup

uv sync
uv run jupyter lab

Structure

• PLAN.md — live design artifact (read this first)
• CLAUDE.md — protocol for AI coding sessions across machines
• STYLE.md — coding and notebook conventions
• notebooks/ — numbered educational notebooks
• src/ntt_edu/ — Python reference implementations
• src/ntt_kernels/ — C++ optimized kernels (Phase B+)
• tests/ — correctness and parity tests
• doc/ — numbered design docs + discussions/ for decision logs
• bench-results/ — JSONL measurements + roofline plots