Number Theoretic Transform

Introduction

Number-theoretic transform (NTT) is the implementation of the discrete Fourier transform (DFT) over number-theoretic foundations; fast number-theoretic transform (FNTT) is the implementation of the fast Fourier transform (FFT) over number-theoretic foundations.

Number-theoretic transform is a fast algorithm for computing convolution. The most commonly used algorithm includes the aforementioned fast Fourier transform. However, FFT has some implementation drawbacks. For example, the data vector must be multiplied by a matrix of complex coefficients, and the real and imaginary parts of each complex coefficient are sine and cosine functions. Therefore, most coefficients are floating-point numbers, meaning that complex and floating-point arithmetic must be performed, resulting in higher computational complexity and larger errors due to floating-point operations.

NTT addresses polynomial multiplication with a modulus, which imposes certain restrictions and often involves large numbers. Currently, the most common modulus is 998244353.

Prerequisites

Learning NTT requires prerequisite knowledge: discrete Fourier transform, generating subgroups, primitive roots, and discrete logarithms. Relevant knowledge can be learned on the corresponding pages and will not be repeated here.

Definition

Number-theoretic Transform

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

Number-theoretic transform (NTT) is obtained by reducing 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\), there exists a primitive \(n\)-th root of unity, so we have \(p=\xi n+1\) for a positive integer \(\xi\). Specifically, for a prime \(p=qn+1, (n=2^m)\), a primitive root \(g\) satisfies \(g^{qn} \equiv 1 \pmod p\). Treating \(g_n=g^q\pmod p\) as the equivalent of \(\omega_n\), it satisfies similar properties, such as \(g_n^n \equiv 1 \pmod p, g_n^{n/2} \equiv -1 \pmod p\).

Since this involves number-theoretic transformations, \(N\) (to distinguish it from \(n\) in FFT, we denote it as \(N\) here) can be larger than \(n\) in FFT. However, simply treat \(\frac{qN}{n}\) as \(q\) here to avoid size issues.

Common examples 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 \]

Here, \(g^{qn}\) is equivalent to \(\mathrm{e}^{2\pi \mathrm{i} n}\).

When iterating to 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

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

The divide-and-conquer method used in FNTT is exactly the same as that used in FFT. This means that by making simple modifications to the FFT code, one can obtain the FNTT code.

In competitive programming, the term NTT often actually refers to the fast number-theoretic transform, and it is generally assumed that "number-theoretic transform" means "fast number-theoretic transform."

This abbreviation follows a similar logic to that of the fast Fourier transform. In fact, the term "fast Fourier transform" (FFT) refers to "fast discrete Fourier transform" (FDFT). However, since "fast" can only be applied to discrete cases, specifically when the order of the primitive root of unity is a power of \(2\), and not to continuous cases, the word "discrete" is omitted, turning FDFT into FFT. Thus, FFT always refers to this special discrete case.

Number-theoretic transform or fast number-theoretic transform operates under modulo arithmetic, which is inherently discrete and never continuous, so there is no need to mention the word "discrete."

In the field of algorithms, operations without speed improvements are meaningless. The term DFT is introduced in the context of FFT because DFT has other specific applications in signal processing and image processing, and DFT is also the principle or prerequisite knowledge for FFT.

When no confusion arises, NTT is often used to refer to FNTT. To avoid further confusion in the following discussion, the terms NTT and FNTT are separated below.

The specific relationships among DFT, FFT, NTT, and FNTT are:

Based on DFT and NTT, adding divide-and-conquer operations yields FFT and FNTT. The method and principle of divide-and-conquer can be found in the fast Fourier transform article.
Based on DFT and FFT, replacing complex addition and multiplication with addition and multiplication modulo \(p\) (generally limited to between \(0\) and \(p-1\)), and replacing the primitive root of unity with a primitive root of the same order modulo \(p\) (with the order being a power of \(2\)), yields NTT and FNTT.

Since the replaced operations only involve addition and multiplication, DFT, FFT, NTT, and FNTT share the same principle and operate on rings satisfying addition and multiplication, without requiring the stricter condition of division operations on fields.

In fact, as long as a primitive root (i.e., a generator in group theory) exists, NTT or FNTT under that modulus can be performed. Considering that moduli \(1\), \(2\), and \(4\) are too small to be practically meaningful, for odd primes \(p\) and positive integers \(\alpha\), as long as a primitive root \(g\) is given for moduli \(p^\alpha\) and \(2p^\alpha\), NTT or FNTT can still be performed using the same method.

Template

Below is a template for large integer multiplication, referenced from here.

Reference Code

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    x = 10 * x + ch - '0';
    ch = getchar();
  }
  return x * f;
}

void print(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

constexpr int N = 300100, 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) {
  int i, j, k, m, gn, g, tmp;
  for (i = 0; i < lim; ++i)
    if (r[i] < i) swap(x[i], x[r[i]]);
  for (m = 2; m <= lim; m <<= 1) {
    k = m >> 1;
    gn = qpow(3, (P - 1) / m);
    for (i = 0; i < lim; i += m) {
      g = 1;
      for (j = 0; j < k; ++j, g = 1ll * g * gn % P) {
        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 (i = 0; i < lim; ++i) x[i] = 1ll * x[i] * inv % P;
  }
}

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

char a[N], b[N];

int main() {
  int i, lim(1), n;
  scanf("%s", a);
  n = strlen(a);
  for (i = 0; i < n; ++i) A[i] = a[n - i - 1] - '0';
  while (lim < (n << 1)) lim <<= 1;
  scanf("%s", b);
  n = strlen(b);
  for (i = 0; i < n; ++i) B[i] = b[n - i - 1] - '0';
  while (lim < (n << 1)) lim <<= 1;
  for (i = 0; i < lim; ++i) r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);
  ntt(A, lim, 1);
  ntt(B, lim, 1);
  for (i = 0; i < lim; ++i) C[i] = 1ll * A[i] * B[i] % P;
  ntt(C, lim, -1);
  int len(0);
  for (i = 0; i < lim; ++i) {
    if (C[i] >= 10) len = i + 1, C[i + 1] += C[i] / 10, C[i] %= 10;
    if (C[i]) len = max(len, i);
  }
  while (C[len] >= 10) C[len + 1] += C[len] / 10, C[len] %= 10, len++;
  for (i = len; ~i; --i) putchar(C[i] + '0');
  puts("");
  return 0;
}

References and Further Reading

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用