AIOJ

Introduction

The number-theoretic transform (NTT) is an implementation of the discrete Fourier transform (DFT) over number theory; the fast number-theoretic transform (FNTT) is the number-theoretic counterpart of the fast Fourier transform (FFT).

The number-theoretic transform is a fast algorithm for computing convolutions. The most commonly used algorithms include the fast Fourier transform introduced earlier. However, the fast Fourier transform has several implementation drawbacks. For example, the data vector must be processed by a matrix of complex coefficients, and the real and imaginary parts of each complex coefficient are sine and cosine functions. Most coefficients are therefore floating-point numbers, so the computation involves complex floating-point arithmetic, which requires more work and produces larger numerical errors.

NTT handles polynomial multiplication under a modulus. In this sense it is subject to restrictions imposed by the modulus, and the numbers involved are relatively large. The most common modulus is 998244353.

Prerequisite knowledge

Learning the number-theoretic transform requires knowledge of the discrete Fourier transform, generated subgroups, primitive roots, and discrete logarithms. These topics are covered on their respective pages and are not repeated here.

Definition

Number-theoretic transform

In mathematics, NTT is the discrete Fourier transform (DFT) over an arbitrary ring. In the case of a finite field, it is usually called the number-theoretic transform (NTT).

The number-theoretic transform (NTT) converts the discrete Fourier transform to $F={\mathbb {Z}/p}$ , the integers modulo a prime $p$ . This is a finite field. As long as $n$ divides $p-1$ , a primitive $n$ -th root exists, so $p=\xi n+1$ for a positive integer $ξ$ . Specifically, for a prime $p=qn+1, (n=2^m)$ , a primitive root $g$ satisfies $g^{qn} \equiv 1 \pmod p$ . Taking $g_n=g^q\pmod p$ as the analogue of $\omega_n$ , we obtain similar properties such as $g_n^n \equiv 1 \pmod p, g_n^{n/2} \equiv -1 \pmod p$ .

Because this involves number theory, $N$ (to distinguish the $n$ in FFT, we call the $n$ here $N$ ) can be larger than the $n$ in FFT. It is enough to regard $\frac{qN}{n}$ as the $q$ here, which avoids size issues.

Common choices include:

p = 167772161 = 5 \times 2^{25}+1, g=3

p = 469762049 = 7 \times 2^{26}+1, g=3

p = 754974721 = 3^2 \times 5 \times 2^{24}+1, g=11

p = 998244353 = 7 \times 17 \times 2^{23}+1, g=3

p = 1004535809 = 479 \times 2^{21}+1, g=3

That is, $g^{qn}$ is the analogue of $\mathrm{e}^{2\pi \mathrm{i} n}$ .

At an iteration of length $l$ , $g_l = g^{\frac{p-1}{l}}$ , or $\omega_n = g_l = g_N^{\frac{N}{l}} = g_N^{\frac{p-1}{l}}$ .

Fast number-theoretic transform

The fast number-theoretic transform (FNTT) is the fast algorithm obtained by adding divide and conquer to the number-theoretic transform (NTT).

The divide-and-conquer method used by the fast number-theoretic transform is exactly the same as that used by the fast Fourier transform. Therefore, only minor modifications to FFT code are needed to obtain FNTT code.

In algorithm competitions, the term NTT often actually refers to the fast number-theoretic transform; it is generally understood that “number-theoretic transform” means “fast number-theoretic transform”.

This abbreviation follows the same logic as for the fast Fourier transform. Strictly speaking, “fast Fourier transform” (FFT) means “fast discrete Fourier transform” (FDFT), but because “fast” can apply only to the discrete transform, including the special case where the primitive root of unity has order $2$ raised to a power, and cannot apply to the continuous transform, “discrete” is omitted: FDFT becomes FFT, which always denotes the special discrete case.

The number-theoretic transform or fast number-theoretic transform is performed modulo a number, so there is no continuous case; it is always discrete, and there is naturally no need to mention “discrete”.

In algorithmic contexts, an operation that is not accelerated is of little significance. DFT is introduced in the FFT discussion because DFT also has other concrete applications in signal and image processing, and because DFT is the principle behind, or a prerequisite for, FFT.

When there is no ambiguity, NTT is commonly used to refer to FNTT. To avoid confusion with the discussion below, the terms NTT and FNTT are distinguished there.

The precise relationships among DFT, FFT, NTT, and FNTT are as follows:

Starting from DFT and NTT, adding divide and conquer yields FFT and FNTT. The method and principle of divide and conquer are described in the article on the fast Fourier transform.
Starting from DFT and FFT, replace complex addition and multiplication with addition and multiplication modulo $p$ , generally restricting values to $0$ through $p-1$ ; replace the primitive root of unity with a primitive root of unity of the same order modulo $p$ , where the order is a power of $2$ . This yields NTT and FNTT.

Because the replacement operations involve only addition and multiplication, DFT, FFT, NTT, and FNTT share the same principle and all operate over rings with addition and multiplication; the stricter requirement of division in a field is unnecessary.

In fact, as long as a primitive root, that is, a generator in group theory, exists, NTT or FNTT can be performed under the modulus. Since moduli $1$ , $2$ , and $4$ are too small to be meaningful in practice, for an odd prime $p$ and a positive integer $\alpha$ , it is enough to provide, for moduli $p^\alpha$ and $2p^\alpha$ , a primitive root $g$ ; the same method still allows NTT or FNTT to be performed.

Template

Library Checker - Convolution

#include <algorithm>
#include <cstdio>
using namespace std;

constexpr int N = 1 << 20, P = 998244353;

int qpow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % P;
    x = 1ll * x * x % P;
    y >>= 1;
  }
  return res;
}

int r[N];

void ntt(int *x, int lim, int opt) {
  for (int i = 0; i < lim; ++i)
    if (r[i] < i) swap(x[i], x[r[i]]);
  for (int m = 2; m <= lim; m <<= 1) {
    int k = m >> 1;
    int gn = qpow(3, (P - 1) / m);
    for (int i = 0; i < lim; i += m) {
      int g = 1;
      for (int j = 0; j < k; ++j, g = 1ll * g * gn % P) {
        int tmp = 1ll * x[i + j + k] * g % P;
        x[i + j + k] = (x[i + j] - tmp + P) % P;
        x[i + j] = (x[i + j] + tmp) % P;
      }
    }
  }
  if (opt == -1) {
    reverse(x + 1, x + lim);
    int inv = qpow(lim, P - 2);
    for (int i = 0; i < lim; ++i) x[i] = 1ll * x[i] * inv % P;
  }
}

int A[N], B[N], C[N];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &A[i]);
  for (int i = 0; i < m; i++) scanf("%d", &B[i]);
  int N = max(n, m), lim = 1;
  while (lim < (N << 1)) lim <<= 1;
  for (int i = 0; i < lim; ++i) r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);
  ntt(A, lim, 1);
  ntt(B, lim, 1);
  for (int i = 0; i < lim; ++i) C[i] = 1ll * A[i] * B[i] % P;
  ntt(C, lim, -1);
  for (int i = 0; i < n + m - 1; i++)
    printf("%d%c", C[i], " \n"[i == n + m - 2]);
  return 0;
}

Number-Theoretic Transform