How to Learn the Number Theoretic Transform: Modular Roots of Unity, Butterflies, Exact Convolution and CRT

Quick Read. The Number Theoretic Transform (NTT) is an FFT-style transform performed in modular arithmetic. It converts polynomial coefficients into evaluations at modular roots of unity, lets convolution become pointwise multiplication, then transforms the result back exactly without floating-point rounding. The beginner should first understand polynomial convolution and modular inverses. The intermediate learner should trace one radix-2 butterfly. The advanced learner should understand primitive roots, transform-length constraints and inverse scaling. The professional should handle modulus choice, CRT reconstruction, overflow, thresholds, vectorisation and verification.

One-sentence answer

The NTT computes a discrete Fourier transform inside a finite field, using modular roots of unity so that polynomial multiplication can be reduced from quadratic convolution to O(n log n) butterfly operations with exact integer arithmetic.

Why this algorithm exists

If two polynomials have n coefficients each, the schoolbook product forms every coefficient pair, taking O(n²) multiplications. FFT-based convolution accelerates this dramatically, but the usual complex-number FFT introduces floating-point error. When coefficients are naturally modulo a prime — common in combinatorics, coding theory, cryptography and competitive programming — exact modular arithmetic is preferable.

The NTT keeps the same strategic idea as the FFT: evaluate, multiply pointwise, interpolate. The difference is the number system. Instead of complex roots of unity, the transform uses elements of a finite field whose powers cycle with exactly the required transform length.

Level 1 — Beginner: understand convolution before transforms

Let A(x) = 1 + 2x + 3x² and B(x) = 4 + 5x. Their product coefficients are convolution sums:

c[0] = 1*4
c[1] = 1*5 + 2*4
c[2] = 2*5 + 3*4
c[3] = 3*5

That pairwise pattern is the problem. If each input contains hundreds of thousands of coefficients, direct multiplication becomes expensive. A transform changes representation so that convolution in coefficient space becomes ordinary pointwise multiplication in evaluation space.

The three-stage picture

Transform A and B from coefficients to evaluations.
Multiply corresponding evaluations.
Apply the inverse transform to recover product coefficients.

Do not start by memorising code. If these three stages are not clear, a butterfly implementation will look like unexplained index manipulation.

Modular roots of unity

An n-th root of unity modulo a prime p is an element ω satisfying ωⁿ ≡ 1 (mod p). For the transform to behave like an n-point DFT, ω must be primitive: no smaller positive exponent should already produce 1.

Because the non-zero elements modulo prime p form a multiplicative group of size p−1, an n-th root of unity exists when n divides p−1. This is why NTT-friendly primes are chosen carefully. A famous example is 998244353 = 119 × 2²³ + 1, which supports power-of-two transform lengths up to 2²³.

Level 2 — Intermediate: one radix-2 butterfly

A radix-2 transform repeatedly combines pairs of partial results. If u and v are the two values and w is the relevant power of the root of unity, the butterfly is:

t = v * w mod p
left  = u + t mod p
right = u - t mod p

The complete iterative algorithm first arranges indices in bit-reversed order, then runs stages of length 2, 4, 8 and so on. At each stage the root step changes so that the correct powers of ω are applied across each block.

ntt(a, invert):
    bit_reverse_permute(a)
    for len = 2, 4, 8, ..., n:
        root = primitive_len_th_root(len)
        if invert:
            root = modular_inverse(root)

        for each block of size len:
            w = 1
            for j in 0 .. len/2-1:
                u = a[left+j]
                v = a[left+j+len/2] * w mod p
                a[left+j]       = u + v mod p
                a[left+j+len/2] = u - v mod p
                w = w * root mod p

    if invert:
        multiply every entry by inverse(n) mod p

The beginner sees additions and multiplications. The intermediate learner should see a recursive decomposition of the DFT into even and odd index groups.

Why the inverse needs n⁻¹

The forward and inverse transforms use reciprocal roots, but composing them yields n times the original sequence. Because arithmetic is modulo p, divide by n by multiplying by its modular inverse n⁻¹. This inverse exists as long as n is not divisible by p — automatically true for standard transform lengths smaller than p.

Polynomial multiplication step by step

Let result_length = |A| + |B| − 1.
Choose n as the next supported power of two at least result_length.
Pad both coefficient arrays to length n with zeros.
Forward-transform both arrays.
Multiply their transformed values componentwise modulo p.
Inverse-transform the product.
Discard the padded tail.

Every step is exact modulo p. That is one of the NTT’s greatest practical advantages over floating-point FFT convolution.

Level 3 — Advanced: choosing a modulus and primitive root

An NTT implementation is not valid merely because p is prime. The transform length must divide p−1, and the chosen root must have the right order. If g is a primitive generator modulo p and n divides p−1, then g^((p−1)/n) is an n-th root of unity. You still need the exact-order condition; using a root of smaller order silently destroys invertibility.

Common implementations use preselected NTT-friendly primes and known primitive generators. That is sensible engineering, but professionals should understand what those constants guarantee rather than treating 998244353 and 3 as magic numbers.

CRT: exact convolution beyond one modulus

One modulus only determines coefficients modulo p. If the true integer coefficients may exceed p, run the convolution under several pairwise-coprime NTT primes and reconstruct each coefficient using the Chinese Remainder Theorem (CRT). The product of the chosen moduli must be large enough to represent the required coefficient range unambiguously.

This is a professional-level transition: the NTT is not merely “FFT without rounding.” It is a family of exact modular transforms that can be composed to recover wider integer results.

Correctness: what should you prove?

The chosen root ω has exact order n.
The modular DFT matrix is invertible because the evaluation points 1, ω, ω², … are distinct.
The radix-2 butterfly computes the same transform as the direct O(n²) definition by splitting even and odd coefficients.
Pointwise multiplication of evaluations corresponds to multiplication of the underlying polynomials modulo xⁿ−1.
Zero-padding prevents cyclic wraparound from corrupting the desired ordinary convolution coefficients.
The inverse transform with reciprocal roots and scaling by n⁻¹ recovers the original coefficient vector.

Complexity

A radix-2 transform has log₂n stages. Each stage performs O(n) modular operations, giving O(n log n) time. The array itself uses O(n) storage, and an iterative in-place transform can keep auxiliary space small. Real performance depends on modular multiplication cost, memory traffic, root-table strategy and the threshold at which NTT overtakes schoolbook multiplication.

Professional engineering

Small-size threshold: schoolbook convolution often wins for tiny arrays because transform setup dominates.
Overflow discipline: intermediate products may exceed a 32-bit type even if the modulus fits in 32 bits. Use a safe wider type or specialised modular multiplication.
Normalization: after subtraction, restore residues to the chosen canonical interval consistently.
Root tables: precomputing stage roots can reduce exponentiation overhead, but tables cost memory and complicate multi-modulus code.
Lazy reduction: carefully allowing values to remain temporarily above p can reduce modulus operations, but only with proved bounds.
CRT reconstruction: use a numerically and overflow-safe reconstruction method when combining several primes.
Vectorisation and cache: butterfly order, contiguous access and modular arithmetic strategy determine throughput on modern CPUs.
Security context: in cryptographic systems, constant-time requirements and side-channel behaviour matter in addition to asymptotic speed.

Testing ladder

Check that forward then inverse NTT returns the original vector for every small supported length.
Compare NTT convolution against O(n²) multiplication on thousands of random small arrays.
Test all-zero, one-term, maximum-residue and repeated-coefficient cases.
Verify transform lengths at the exact modulus limit.
For CRT, generate coefficients near the reconstruction bound and compare with big-integer arithmetic.
Benchmark the crossover point between schoolbook and NTT multiplication rather than guessing it.

Common misconceptions

“Any prime modulus works.” The required transform length must divide p−1.
“Any non-zero root works.” The root must have the exact required multiplicative order.
“Pointwise multiplication automatically gives ordinary convolution.” Without sufficient zero-padding, the transform computes cyclic convolution.
“NTT is always faster.” For short inputs, O(n²) multiplication may win.
“CRT removes every range problem.” The combined modulus product still must exceed the range needed for unique reconstruction.

A learning route from beginner to professional

Beginner: multiply two short polynomials by hand and write the convolution formula.
Intermediate: implement modular exponentiation, inverses and a four-point NTT; trace every butterfly.
Advanced: write a generic radix-2 convolution routine and prove the root-order and inverse conditions.
Algorithm engineer: add threshold switching, root caching and careful overflow handling.
Professional: support multiple NTT primes and CRT, profile memory and arithmetic bottlenecks, and validate against independent big-integer or symbolic implementations.

For learning, use worked transformations rather than starting from production code. Ask learners to predict a butterfly’s two outputs before executing it, then explain why the chosen root power appears at that position. Programming-education research supports this progression from worked examples and tracing toward modification and independent construction.

Authoritative sources and further reading

J. M. Pollard, The Fast Fourier Transform in a Finite Field, Mathematics of Computation 25, 1971.
S.-W. Chiu and K. K. Parhi, Long Polynomial Modular Multiplication using Low-Complexity Number Theoretic Transform, tutorial treatment of NTT-based modular multiplication.
Algorithms for Competitive Programming: FFT and Number Theoretic Transform, a practical implementation reference.
Y. Shin et al., Worked-Out Example and Metacognitive Scaffolding in Programming, 2023.
X. Hou, B. Ericson and X. Wang, Using Adaptive Parsons Problems to Scaffold Write-Code Problems, ICER 2022.

Closing idea. The NTT becomes much easier once you separate the algebra from the loops. First understand why roots of unity make evaluation invertible and why convolution becomes pointwise multiplication. Only then optimise the butterflies. The professional implementation is fast because the mathematics is exact, not because the mathematics can be ignored.