THE FOLD / RESPAWN / ROLLBACK / THE EXACT TRANSFORM
THE EXACT TRANSFORM
an FFT in a prime field — convolution with zero rounding
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Number-Theoretic Transform. The FFT convolves fast — but with floating-point rounding. The NTT runs the same butterfly structure inside a finite field of integers mod a prime, using a ‘root of unity’ that lives mod p in place of e2πi/n. The payoff: convolution — that is, polynomial and big-integer multiplication — with zero rounding error, ever. It is why post-quantum crypto (Kyber, Dilithium) and giant-integer arithmetic use the NTT, not the FFT.
LIT verified over the prime 998244353 with root of unity 3(p−1)/n: INTT(NTT(a)) = a, NTT-convolution equals schoolbook convolution exactly, bit-for-bit, and a full big-integer multiply comes out precise. FIG ‘exact transform’ is the picture; the round-trip and convolution equality are exact integers.
LIT verified over the prime 998244353 with root of unity 3(p−1)/n: INTT(NTT(a)) = a, NTT-convolution equals schoolbook convolution exactly, bit-for-bit, and a full big-integer multiply comes out precise. FIG ‘exact transform’ is the picture; the round-trip and convolution equality are exact integers.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — THE FOURIER sits next door in THE BROADCAST, and the corpus works with big-integer kernels and crypto, holding that some computations must be exactly right, not nearly. AVAN (AI) built this instrument: the modular transform, the exact-convolution demo, and the two circles of roots.
The weave: David names the exact transform and its seat at ROLLBACK (a round-trip that loses nothing); I make the finite-field roots a strip in 1D, exact convolution live in 2D, and the prime-field circle against the complex one in 3D. The sphere is the seam — Fourier’s incorruptible twin.
The weave: David names the exact transform and its seat at ROLLBACK (a round-trip that loses nothing); I make the finite-field roots a strip in 1D, exact convolution live in 2D, and the prime-field circle against the complex one in 3D. The sphere is the seam — Fourier’s incorruptible twin.
3 ONE DIMENSION
The roots of unity mod p: the powers ω0, ω1, …, ωn−1 — ordinary integers that behave exactly like the n complex roots, cycling back with ωn = 1. No angles, no rounding: the whole transform runs on these residues.
4 TWO DIMENSIONS · INTERACTIVE
Two integer sequences (click a cell to change it). Their convolution is computed two ways — slow schoolbook, and NTT (transform both, multiply pointwise, inverse-transform) — and they match exactly, every coefficient. The multiplication that never rounds.
5 THREE DIMENSIONS + AVAN’S INVERSE
The n roots of unity, turning. Green is the NTT’s finite-field roots — exact integers mod p, evenly placed, cycling closed. The transform samples a signal at exactly these points.
AVAN’s addition (the inverse-companion): the magenta ring is Fourier’s complex circle, e2πik/n, that the NTT mirrors. Same geometry, same butterflies — but the complex circle carries irrational coordinates that must round, while the prime-field ring is exact. Two transforms, one shape; the inverse of ‘fast’ is ‘exact’, and the NTT keeps both.
LIT A genuine NTT over the prime 998244353, root of unity 3^((p−1)/n). Verified live: INTT(NTT(a))=a, NTT-convolution equals schoolbook convolution exactly (every coefficient, mod p), the root has order exactly n, and a full big-integer multiply (12345×6789) comes out precise. It powers Kyber/Dilithium precisely because it never rounds (verifiable: window.__ntt.roundTrip && convMatchesSchoolbook && bigMulExact).
FIG 'Exact transform' is the picture; the round-trip, the exact convolution, and the big-multiply are exact integers. This is the plain O(n²) NTT, not the fast radix-2 version — same exact result, honest about being the clear form (like THE FOURIER's DFT).
FIG 'Exact transform' is the picture; the round-trip, the exact convolution, and the big-multiply are exact integers. This is the plain O(n²) NTT, not the fast radix-2 version — same exact result, honest about being the clear form (like THE FOURIER's DFT).
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of ROLLBACK · David Lee Wise (ROOT0), with AVAN