Number Theoretic Transform
Overview
The number theoretic transform (NTT) is the discrete Fourier transform (DFT) carried out in a number-theoretic setting; the fast number theoretic transform (FNTT) is the fast Fourier transform (FFT) carried out in a number-theoretic setting.
The number theoretic transform is a fast algorithm for computing convolutions. The most widely used algorithms for this include the fast Fourier transform mentioned above. But the fast Fourier transform has some drawbacks in implementation. For example, the data vector has to be multiplied by a matrix of complex coefficients, and the real and imaginary parts of each complex coefficient are values of the sine and cosine functions, so most of the coefficients are floating-point numbers. In other words, the arithmetic has to be complex and floating-point, which makes the computation expensive and the floating-point error large.
The NTT handles polynomial multiplication under a modulus. It is somewhat restricted by the modulus, and the numbers involved are fairly large. The most common modulus today is 998244353.
Prerequisites
To learn the number theoretic transform you need to know the discrete Fourier transform, generated subgroups, primitive roots and discrete logarithms. These topics are covered on their own pages and are not repeated here.
Definition
Number theoretic transform
In mathematics, the NTT is the discrete Fourier transform (DFT) over an arbitrary ring. Over a finite field, it is usually called the number theoretic transform (NTT).
The number theoretic transform (NTT) is obtained by specializing the discrete Fourier transform to \(F={\mathbb {Z}/p}\), the integers modulo a prime \(p\). This is a finite field, and a primitive \(n\)-th root of unity exists whenever \(n\) divides \(p-1\), 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\). Treat \(g_n=g^q\pmod p\) as the counterpart of \(\omega_n\): it has similar properties, such as \(g_n^n \equiv 1 \pmod p\) and \(g_n^{n/2} \equiv -1 \pmod p\).
Because we are dealing with a number theoretic transform here, \(N\) (we call the \(n\) of this section \(N\) to tell it apart from the \(n\) of the FFT) may be larger than the \(n\) of the FFT, but it is enough to treat \(\frac{qN}{n}\) as the \(q\) here, and that avoids any problem with size.
Common choices are:
That is, \(g^{qn}\) corresponds to \(\mathrm{e}^{2\pi \mathrm{i} n}\).
When the iteration reaches length \(l\), we have \(g_l = g^{\frac{p-1}{l}}\), or \(\omega_l = g_l = g_N^{\frac{N}{l}} = g^{\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).
Its divide and conquer is exactly the same as that of the fast Fourier transform. So a few simple modifications turn code for the fast Fourier transform into code for the fast number theoretic transform.
In competitive programming, the term NTT usually refers in fact to the fast number theoretic transform: "number theoretic transform" is taken by default to mean "fast number theoretic transform".
The logic of this shorthand is much the same as for the fast Fourier transform. The term "fast Fourier transform" (FFT) really means "fast discrete Fourier transform" (FDFT). But "fast" can only apply to the discrete case, and indeed only to the special case where the order of the primitive root of unity is a power of \(2\); it cannot apply to the continuous case. So the word "discrete" is left out and FDFT becomes FFT: FFT always refers to the special discrete case.
The number theoretic transform and the fast number theoretic transform work modulo a number. There is no continuous case: they are always discrete, so the word "discrete" never needs to be mentioned.
In algorithms, an operation that has not been sped up is pointless. The article on the fast Fourier transform introduces the term DFT because the DFT has other concrete applications of its own, in signal processing and image processing, and because the DFT is the principle behind the FFT, or a prerequisite for it.
Where no confusion can arise, NTT is commonly used to mean FNTT. To avoid confusion in the discussion that follows, the two terms NTT and FNTT are kept apart below.
The precise relation between DFT, FFT, NTT and FNTT is as follows:
-
Adding divide and conquer to the DFT and the NTT gives the FFT and the FNTT. For how the divide and conquer works and why, see the article on the fast Fourier transform.
-
Starting from the DFT and the FFT, replace complex addition and complex multiplication by addition and multiplication modulo \(p\), with values usually kept between \(0\) and \(p-1\), and replace the primitive root of unity by a primitive root of unity of the same order modulo \(p\), the order being a power of \(2\). This gives the NTT and the FNTT.
The operations that are replaced are only addition and multiplication, so DFT, FFT, NTT and FNTT all rest on the same principle. They are all carried out over a ring, which has addition and multiplication, and do not need the stricter condition of a field, which also has division.
In fact, the NTT or FNTT can be carried out for any modulus that has a primitive root, that is, a generator in the language of group theory. The moduli \(1\), \(2\) and \(4\) are too small to be of any practical use. For an odd prime \(p\) and a positive integer \(\alpha\), given a primitive root \(g\) for the moduli \(p^\alpha\) and \(2p^\alpha\), the same method still lets us carry out the NTT or FNTT.
Template
Library Checker - Convolution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | |
References and further reading
- FWT (Fast Walsh Transform) Explained from Scratch qaq (ACM/OI) (in Chinese)
- FFT (Fast Fourier Transform) Explained from Scratch! With NTT (ACM/OI) (in Chinese)
- Number-theoretic transform(NTT) - Wikipedia
- Tutorial on FFT/NTT—The tough made simple. (Part 1)
- NTT Template - BlackJack_ CSDN Blog (in Chinese)
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: ChungZH, Yukimaikoriya, tigerruanyifan, isdanni, Saisyc, 383494, Tiphereth-A, XuYueming520, henryrabbit, Xeonacid, sshwy, 24OI-bot, Ir1d, ouuan, GeZiyue, O-Omega, ranwen, Enter-tainer, YifanRuan, ksyx, shuzhouliu, Great-designer, billchenchina, CCXXXI, c-forrest, killcerr, weiwch, HeRaNO (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.