Number Theoretic Transform (NTT)

Every code listing from this chapter of Applied Post-Quantum Cryptography — 2 in total, 2 runnable here. Edit any cell and press Run.

The book's snippets build on each other down the chapter, but a Sage Cell kernel runs one cell and keeps no state afterwards, so each cell replays the earlier listings with apqc_book. That call is the only thing added to the book's own code.

← the playground

Listing 1 — Finding a root in a toy field

The nonzero elements of 𝔽₁₇ form a group of order 16. If g is a generator, then g² has order 8 and can serve as ω for an 8-point cyclic NTT. SageMath can check that condition directly:

Listing 2 — A complete toy cyclic NTT

The following SageMath program performs a complete forward transform, pointwise product, and inverse transform in the cyclic ring 𝔽₁₇[x]/(x⁸-1). It is intentionally a toy model, not ML-KEM.