Number-Theoretic Transform (NTT)

1. Definition and History

The Number-Theoretic Transform (NTT) is a discrete Fourier transform defined over a finite field $\mathbb{Z}/p\mathbb{Z}$ (with $p$ prime) instead of the complex field $\mathbb{C}$. It preserves the mathematical structure of the FFT while operating entirely on integer modular arithmetic, so round-off error never arises.

Historical Timeline

Correspondence between FFT and NTT

Figure 1: NTT inherits the algorithmic structure of the FFT (Cooley-Tukey divide-and-conquer, butterfly operations) and only swaps the underlying field from the complex numbers to a finite field. Only the choice of $\omega$ differs.

2. Primitive Roots and Primitive $N$-th Roots

Primitive Root

For a prime $p$, the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^* = \{1, 2, \ldots, p-1\}$ is a cyclic group of order $p - 1$. An element $g$ that generates this group is called a primitive root:

The order of $g$ equals $p - 1$ (no smaller positive integer $k$ satisfies $g^k \equiv 1 \pmod p$).

Existence and Count

• Existence: a primitive root exists for every prime $p$ (Gauss, 1801)
• Number: $\varphi(p - 1)$ primitive roots, where $\varphi$ is Euler's totient
• Algorithm: try $g = 2, 3, 5, \ldots$; for each prime factor $q$ of $p - 1$ verify that $g^{(p-1)/q} \not\equiv 1 \pmod p$. A primitive root is typically found within $O(\log p)$ trials

Primitive $N$-th Roots

When $N \mid (p - 1)$, the element $\omega = g^{(p-1)/N} \bmod p$ is a primitive $N$-th root of unity in $\mathbb{Z}/p\mathbb{Z}$:

• $\omega^N \equiv 1 \pmod p$ ($N$-th root of unity)
• $\omega^k \not\equiv 1 \pmod p$ for $0 < k < N$ (primitivity)
• $\omega^{N/2} \equiv -1 \pmod p$ (the "halving" property used by the FFT butterfly)

This $\omega$ is the NTT analogue of $e^{-j 2\pi / N}$. It satisfies the same FFT properties:

• Periodicity: $\omega^{k + N} = \omega^k$
• Symmetry: $\omega^{k + N/2} = -\omega^k$
• Halving: $\omega^2$ is a primitive $(N/2)$-th root of unity

These properties license the Cooley-Tukey divide-and-conquer structure verbatim.

3. NTT Formulation and Its Correspondence with FFT

Transform Definition

The NTT of an integer sequence $\{a[n]\}_{n=0}^{N-1}$ (with $a[n] \in \mathbb{Z}/p\mathbb{Z}$) is:

The inverse transform (INTT) is:

Here $N^{-1}$ is the modular inverse of $N$ (computed as $N^{p-2} \bmod p$ via Fermat's little theorem), and $\omega^{-1} = \omega^{N-1} \bmod p$.

Matrix Form

The NTT is a linear transform and admits a matrix representation:

$\Omega_N$ is a symmetric Vandermonde-type matrix whose inverse is $\Omega_N^{-1} = N^{-1} \cdot \overline{\Omega_N}$ (with $(\overline{\Omega_N})_{k,n} = \omega^{-kn}$) — exactly mirroring the FFT.

Convolution Theorem

Side-by-Side Properties

4. NTT-Friendly Primes

Running an NTT of length $N = 2^m$ requires $2^m \mid (p - 1)$ (so that $\omega = g^{(p-1)/N}$ is well-defined as an integer power). A prime $p$ in which $p - 1$ contains a large power-of-two factor is called NTT-friendly:

Major NTT-Friendly Primes

Bit Width versus Use Case

2-Adic Valuation of $p - 1$

The exponent $a$ such that $p - 1 = c \cdot 2^a$ with $c$ odd is the 2-adic valuation $\nu_2(p - 1) = a$. This single number determines the maximum NTT length $N_{\max} = 2^a$. Searching for NTT-friendly primes amounts to generating primes with large $\nu_2(p - 1)$.

5. Fast Modular Arithmetic (Montgomery / Barrett)

The inner loop of an NTT is dominated by "multiply plus reduce mod $p$". A naive (a * b) % p is slow because integer division is slow on modern CPUs. Production implementations therefore replace divisions entirely.

Montgomery Multiplication

Introduced by Peter L. Montgomery in 1985. Choose $R = 2^k$ with $p < R$ (typically $k = 32$ or $64$) and keep every value in Montgomery form $\tilde{a} = a R \bmod p$. The Montgomery product is:

executed without division (Montgomery reduction). Only a single shift by $\log_2 R$ replaces the division.

Barrett Reduction

Introduced by Paul Barrett in 1986. Pre-compute $\mu = \lfloor 2^{2k} / p \rfloor$ once; then for any $0 \le x < p^2$:

The result is $x \bmod p$ or $x \bmod p + p$, so a final conditional subtraction is required. Unlike Montgomery, no pre/post conversion of inputs is needed.

Comparison

Solinas Primes (Special-Form Primes)

Primes of the form $p = 2^a - c$ (small $c$) or $p = 2^a + 2^b - 1$ admit specialised modular reduction (Solinas, 1999):

Combined with Montgomery in the NTT hot loop, this can eliminate all division-like instructions. Mersenne primes $2^{31} - 1$ and $2^{61} - 1$ are special cases of Solinas primes.

6. Algorithm

The NTT algorithm has exactly the same structure as the Cooley-Tukey FFT — only the complex multiplications are replaced by modular ones. An in-place iterative (decimation-in-time) version:

function ntt(a, N, p, omega):
    // Step 1: bit-reversal permutation
    a = bit_reverse_copy(a, N)
    // Step 2: layered butterflies
    for s = 1 to log2(N):
        m = 2^s
        wm = power(omega, N/m, p)        // m-th root = omega^{N/m}
        for k = 0 to N-1 step m:
            w = 1
            for r = 0 to m/2-1:
                t = (w * a[k + r + m/2]) mod p
                u = a[k + r]
                a[k + r]       = (u + t) mod p
                a[k + r + m/2] = (u - t + p) mod p
                w = (w * wm) mod p
    return a

Cost per Pass

• Number of butterflies: $\tfrac{N}{2} \log_2 N$ (identical to FFT)
• Per butterfly: 1 multiply + 2 add/sub (all mod $p$)
• Total: $O(N \log N)$ modular multiplications

Montgomery-Form NTT

In practice every value is held in Montgomery form, and the inner-loop w * a[...] is executed via Montgomery multiplication. Powers of $\omega$ are pre-computed in Montgomery form:

// Pre-compute Montgomery-form roots
omega_mont = (omega * R) mod p
wm_table[s] = (omega^{N/(2^s)} * R) mod p  for s = 1..log2(N)

// Hot inner loop (no division anywhere)
for r = 0 to m/2-1:
    t = MontMul(w, a[k+r+m/2])
    a[k+r+m/2] = SubMod(a[k+r], t)
    a[k+r]     = AddMod(a[k+r], t)
    w = MontMul(w, wm_table[s])

Parallelism

• SIMD: AVX-512 VPMULQ with Montgomery reduction supports eight-way parallel modular multiplication
• GPU: warp-level implementations are published in cuFHE and elsewhere
• Multi-core: the outer loops over butterfly stages parallelise cleanly with $O(\log N)$ synchronisation barriers

The inverse NTT is obtained by replacing $\omega$ with $\omega^{-1}$ and multiplying every output by $N^{-1} \bmod p$ — perfectly symmetric to the forward transform.

7. Negacyclic NTT and $\mathbb{Z}_p[x]/(x^N+1)$

The standard NTT computes a cyclic convolution (modulo $x^N - 1$). Lattice cryptography (Ring-LWE) instead requires an anti-cyclic (negacyclic) convolution modulo $x^N + 1$. The negacyclic NTT computes this directly.

The Anti-Cyclic Convolution

In the polynomial ring $\mathbb{Z}_p[x]/(x^N + 1)$ we have $x^N \equiv -1$, so shifting coefficients flips signs:

The ordinary cyclic convolution is therefore unsuitable for ring multiplication.

Construction of the Negacyclic NTT

Take a primitive $2N$-th root of unity $\psi$ (which requires $2N \mid (p - 1)$, so $\psi^N \equiv -1 \pmod p$) and "twist" the coefficients before transforming:

Apply the standard length-$N$ NTT to $\tilde{a}$. After pointwise multiplication, an inverse twist $\psi^{-n}$ recovers the product in $\mathbb{Z}_p[x]/(x^N + 1)$.

The twist and untwist cost $O(N)$ each — negligible compared to the $O(N \log N)$ transform.

8. Polynomial Multiplication and CRT Composition

To compute the product $h(x) = f(x) \cdot g(x)$ of polynomials of degrees $n$ and $m$, the result has degree $n + m$ and $n + m + 1$ coefficients.

The complexity is $O(N \log N)$ versus the direct cost $O(nm)$ — a dramatic speed-up for large polynomials.

When Coefficients Exceed the Modulus: CRT Composition

If the product coefficients $c_i$ can exceed $p$ — so that $c_i \bmod p$ collides — perform the NTT product in parallel under several NTT-friendly primes $p_1, p_2, p_3$ and recombine with the Chinese Remainder Theorem (CRT):

1. Run NTT products under $p_1 = 998244353$, $p_2 = 985661441$, $p_3 = 754974721$ (or similar)
2. For each coefficient $c_i$, obtain $c_i \bmod p_j$ ($j = 1, 2, 3$)
3. Recover $c_i \bmod (p_1 p_2 p_3)$ via the Garner algorithm (incremental CRT)

Garner Algorithm

Efficient 3-prime CRT recovery:

// Input: x mod p1, x mod p2, x mod p3
// Output: x mod (p1*p2*p3)
inv_12 = modinv(p1, p2)
inv_123 = modinv(p1*p2 mod p3, p3)
v1 = x_mod_p1
v2 = (x_mod_p2 - v1) * inv_12 mod p2
v3 = ((x_mod_p3 - v1) - v2*p1) * inv_123 mod p3
return v1 + v2*p1 + v3*p1*p2

Implementation in sangi

The sangi library implements a 5-smooth NTT on sizes $N = 2^a 3^b 5^c$ with radix-3 and radix-5 butterflies. The set of usable sizes is much denser than the standard $N = 2^k$ alone, so the NTT engages for a wider class of inputs. The construction follows the mixed-radix Cooley-Tukey idea applied to NTT.

9. Multiprecision Integer Multiplication (Schönhage-Strassen)

To multiply $d$-digit integers $A, B$ with NTT:

1. Represent each integer as a coefficient sequence in base $B$ (e.g.\ $B = 2^{16}$ or $B = 10^4$), giving polynomials of length $L = \lceil d / \log_B \rceil$
2. NTT-multiply the polynomials to obtain the "digit" coefficients of $A \cdot B$ (which may exceed $B$)
3. Carry propagation: split each $c_i$ into $c_i \bmod B$ plus a carry $\lfloor c_i / B \rfloor$ into the next position

The complexity is $O(d \log d \log \log d)$ (Schönhage-Strassen), or $O(d \log d \cdot 2^{O(\log^* d)})$ (Fürer 2007), and finally $O(d \log d)$ (Harvey-van der Hoeven 2019). This is asymptotically faster than schoolbook $O(d^2)$, Karatsuba $O(d^{1.585})$, and Toom-Cook $O(d^{1.465})$.

The Schönhage-Strassen Algorithm

The classical 1971 NTT-based integer-multiplication algorithm:

1. Split: divide $A, B$ into $K$ blocks, treating them as polynomials of length $L = 2K$
2. Work modulo $2^M + 1$: each coefficient is $M$ bits wide, with $M = O(d^{1/2})$ a typical choice
3. Length-$L$ NTT: $\omega = 2^{M/L}$ becomes a primitive $L$-th root of unity
4. Coefficient products: products of $M$-bit numbers are computed recursively by the same algorithm ($\log \log d$ levels of recursion)
5. Inverse NTT plus carry propagation

NTT modulo $2^M + 1$

The Schönhage-Strassen variant works in the residue ring $\mathbb{Z}/(2^M + 1)\mathbb{Z}$ instead of $\mathbb{Z}_p$. $2$ becomes a primitive $2M$-th root of unity ($2^{2M} = (2^M)^2 \equiv (-1)^2 = 1$, plus primitivity), so $\omega = 2^{2M/L}$ multiplications reduce to bit shifts. This is the algorithm's signature speed-up.

Modern Library Implementations

Real implementations follow a hybrid strategy: schoolbook/Karatsuba for small inputs, Toom-Cook for medium, NTT for large. Crossover thresholds depend on hardware and implementation.

10. Lattice-Based and Post-Quantum Cryptography

The NIST-standardised post-quantum cryptography (PQC) schemes CRYSTALS-Kyber and CRYSTALS-Dilithium (2024) both rely on NTT for fast polynomial-ring arithmetic.

Ring-LWE and Polynomial Arithmetic

The Ring Learning With Errors (RLWE) problem is set in the polynomial ring $R = \mathbb{Z}_p[x]/(x^N + 1)$:

Recovering the secret $s$ is computationally hard. With $a, s, e \in R$ as polynomials of degree $N - 1$ for fairly large $N$ ($256, 512, 1024$), the product $a \cdot s$ dominates the cost and is sped up to $O(N \log N)$ by the NTT.

Major PQC Schemes

NTT in Fully Homomorphic Encryption (FHE)

BFV, BGV, and CKKS — all based on the same polynomial-ring structure — use NTT in encryption, decryption, and homomorphic multiplication. Standard libraries (Microsoft SEAL, IBM HElib, Lattigo) implement NTT pervasively.

Side-Channel Resistance and Constant-Time Implementation

NTT for cryptographic use must be implemented in constant time. Data-dependent branches or memory accesses leak secret values through timing attacks. The final conditional subtraction in Montgomery reduction is replaced by a masked branchless form (always subtract, then mask-select the right value).

11. Competitive Programming

"Convolution mod $p$" is a recurring competitive-programming theme, and the NTT is an essential technique.

Typical Problems

• Polynomial multiplication: product of degree-$10^5$ polynomials mod $998244353$
• Convolution counting: $c_k = \sum_{i+j=k} a_i b_j$
• Subset-sum counts: generating functions for combinatorial enumeration
• Formal power series: $\exp, \log, \sqrt{}, \mathrm{inv}$ truncated mod $x^n$ via Newton iteration + NTT

Arbitrary-Modulus Convolution

Problems often demand convolution under a modulus other than $998244353$ (e.g.\ $10^9 + 7$). The standard recipe is the three-prime NTT: run independent NTTs under $p_1, p_2, p_3$ and apply Garner to reconstruct the target. Total cost is roughly $3$–$4 \times$ a single NTT.

AtCoder Library Convolution

The AtCoder Library (ACL) C++ template atcoder::convolution<Mod> ships an NTT-based convolution that picks the optimal strategy automatically. It is fastest at $\mathrm{Mod} = 998244353$ but supports other moduli too.

12. NTT vs FFT Comparison

When to Choose Which

• Continuous values, approximation acceptable: FFT (signal processing, PDE solvers)
• Exact integer results required: NTT (bigint, cryptography, competitive programming)
• Arbitrary $N$ with no 2-adic constraint: FFT plus Bluestein fall-back
• Fixed $N$, speed paramount: NTT (Kyber/Dilithium)

13. Worked Examples

Example 1: Minimal NTT with $p = 5$, $N = 4$

Example 2: Polynomial Product mod $998244353$

Example 3: Polynomial Multiplication in the Kyber Ring ($p = 3329, N = 256$)

// Convert inputs a, b to Montgomery form
// negacyclic NTT pre-twist: a'[i] = psi^i * a[i]
// Standard 256-point NTT
// Pointwise product
// Inverse 256-point NTT
// post-twist: a[i] = psi^{-i} * a'[i]

14. FAQ

15. References

Original Papers and Key Results

• J. M. Pollard, "The fast Fourier transform in a finite field," Math. Comp., 25(114), pp. 365–374, 1971. (Mathematical prototype of the NTT)
• A. Schönhage & V. Strassen, "Schnelle Multiplikation großer Zahlen," Computing, 7, pp. 281–292, 1971. (NTT-based integer multiplication)
• P. L. Montgomery, "Modular multiplication without trial division," Math. Comp., 44(170), pp. 519–521, 1985.
• D. Harvey & J. van der Hoeven, "Integer multiplication in time $O(n \log n)$," Annals of Math., 193(2), pp. 563–617, 2021.
• V. Lyubashevsky, C. Peikert & O. Regev, "On ideal lattices and learning with errors over rings," J. ACM, 60(6), 2013. (Ring-LWE)

Books

• J. von zur Gathen & J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
• D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997.
• R. E. Blahut, Fast Algorithms for Signal Processing, Cambridge University Press, 2010.
• D. J. Bernstein, J. Buchmann & E. Dahmen (eds.), Post-Quantum Cryptography, Springer, 2009.

Implementation in sangi (cross-links)

• sangi — Integer multiplication algorithms — Karatsuba → Toom-3/4/6/8 → 5-smooth NTT hybrid strategy and thresholds
• sangi — FFT API — C++ interface for the NTT/FFT modules underlying multiprecision multiplication

Related Chapters

• Discrete Fourier and FFT (chapter hub)
• Discrete Fourier Transform (DFT) — the transform computed by NTT
• Fast Fourier Transform (FFT) — overview
• Cooley-Tukey FFT — the algorithmic ancestor of NTT
• Bluestein FFT — arbitrary-length DFT; finite-field analogue exists

Online Resources

• Wikipedia: Number-theoretic transform
• Wikipedia: Schönhage-Strassen algorithm
• AtCoder Library — Convolution
• CRYSTALS Suite (Kyber/Dilithium)
• FLINT