Project Nayuki


Number-theoretic transform (integer DFT)

Introduction

The NTT is a generalization of the classic DFT to finite fields. With a lot of work, it basically lets one perform fast convolutions on integer sequences without any round-off errors, guaranteed. Convolutions are useful for multiplying large numbers or long polynomials, and the NTT is asymptotically faster than other methods like Karatsuba multiplication.

Review of the complex DFT

The classic discrete Fourier transform (DFT) operates on vectors of complex numbers:

  1. Suppose the input vector has length \(n\). The output vector will also have length \(n\).

  2. Let \(ω\) (omega) be a primitive \(n\)th root of unity. In other words, \(ω^n = 1\), but \(ω^k \ne 1\) for all integers \(1 \le k < n\). The standard choice for the DFT is \(ω = e^{-2πi/n}\).

  3. Each output element equals a particular weighted sum of all input elements, using some powers of \(ω\) as weights. Denoting the input vector as \(X\) and the output vector as \(Y\), we have (with 0-based indexing): \(Y(k) = X(0) ω^{0k} + X(1) ω^{1k} + X(2) ω^{2k} + ... + X(n-1) ω^{(n-1)k}\).

  4. The inverse transform, which restores the original vector, is given by: \(X(k) n = Y(0) ω^{-0k} + Y(1) ω^{-1k} + Y(2) ω^{-2k} + \cdots + Y(n-1) ω^{-(n-1)k}\).

Additional notes:

Procedure for the NTT

  1. Suppose the input vector is a sequence of \(n\) non-negative integers.

  2. Choose a minimum working modulus \(M\) such that \(1 \le n < M\) and every input value is in the range \([0, M)\).

  3. Select some integer \(k \ge 1\) and define \(N = kn + 1\) as the working modulus. We require \(N \ge M\), and \(N\) to be a prime number. Dirichlet’s theorem guarantees that for any \(n\) and \(M\), there exists some choice of \(k\) to make \(N\) be prime.

  4. Because \(N\) is prime, the multiplicative group of \(\mathbb{Z}_N\) has size \(φ(N) = N-1 = kn\). Furthermore, the group must have at least one generator \(g\), which is also a primitive \((N-1)\)th root of unity.

  5. Define \(ω \equiv g^k \text{ mod } N\). We have \(ω^n = g^{kn} = g^{N-1} = g^{φ(N)} \equiv 1 \text{ mod } N\) due to Euler’s theorem. Furthermore because \(g\) is a generator, we know that \(ω^i = g^{ik} \not\equiv 1\) for \(1 \le i < n\), because \(ik < nk = N-1\). Hence \(ω\) is a primitive \(n\)th root of unity, as required by the DFT of length \(n\).

  6. The rest of the procedure for the forward and inverse transforms is identical to the complex DFT. Moreover, the NTT can be modified to implement a fast Fourier transform algorithm such as Cooley-Tukey.

Additional notes:


Examples

Source code

More info