ii. Number-Theoretic Transform

The FFT over ${\mathbb{Z}}_p$: for a prime $p=c\cdot 2^k+1$, $(\mathbb{Z}/p{)}^{\ast }$ is cyclic of order $c\cdot 2^k$, so it contains a primitive $2^j$-th root of unity for every $j\le k$, and the Cooley–Tukey algorithm runs verbatim with exact integer arithmetic. This note’s block is the shared polynomial core of the chapter: ntt, convolution (templated on the Mint<P> of Modular Arithmetic), Poly = vector<mint> with polyMul, and the three-prime CRT convolution for an arbitrary modulus. Later notes (power series, evaluation, recurrences, counting) assume it.

Prime	Form	Max length	Primitive root
998244353	$119\cdot 2^{23}+1$	$2^{23}$	3
167772161	$5\cdot 2^{25}+1$	$2^{25}$	3
469762049	$7\cdot 2^{26}+1$	$2^{26}$	3
1004535809	$479\cdot 2^{21}+1$	$2^{21}$	3
754974721	$45\cdot 2^{24}+1$	$2^{24}$	11
2013265921	$15\cdot 2^{27}+1$	$2^{27}$	31
4179340454199820289	$29\cdot 2^{57}+1$	$2^{57}$	3 (needs 128-bit products)

$10^9+7$ is not NTT-friendly ($p-1=2\cdot 500000003$), which is why 998244353 is the standard contest modulus. For an arbitrary modulus $m$: (1) three primes + CRT (below): the exact convolution value is $<n(m-1{)}^2<998244353\cdot 167772161\cdot 469762049\approx 7.9\cdot 10^{25}$ for $m\le 10^9+7$, $n\le 10^6$, so CRT reconstructs it exactly; (2) coefficient splitting with the complex FFT (convMod in FFT); (3) __int128 accumulation for small $n$.

constexpr ll powC(ll b, ll e, ll m) { ll r = 1; for (b %= m; e; e >>= 1, b = b * b % m) if (e & 1) r = r * b % m; return r; }
template <int P> constexpr int nonResidue() { int g = 2; while (powC(g, (P - 1) / 2, P) != P - 1) g++; return g; }
 
template <int P> void ntt(vector<Mint<P>>& a, bool invert = false) {   // n a power of two dividing P - 1
    using Z = Mint<P>; int n = sz(a); if (n <= 1) return;
    static vector<Z> roots{0, 1};                           // roots[k + j] = w_{2k}^j
    if (sz(roots) < n) {
        constexpr int g = nonResidue<P>(); int k = __builtin_ctz(sz(roots)); roots.resize(n);
        for (; (1 << k) < n; k++) {
            Z e = Z(g).pow((P - 1) >> (k + 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) roots[2 * i] = roots[i], roots[2 * i + 1] = roots[i] * e;
        }
    }
    for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) swap(a[i], a[j]); }
    for (int k = 1; k < n; k *= 2)
        for (int i = 0; i < n; i += 2 * k) for (int j = 0; j < k; j++) {
            Z u = a[i + j], v = a[i + j + k] * roots[k + j];
            a[i + j] = u + v; a[i + j + k] = u - v;
        }
    if (invert) { reverse(a.begin() + 1, a.end()); Z inv = Z(n).inv(); for (Z& x : a) x *= inv; }
}
 
template <int P> vector<Mint<P>> convolution(vector<Mint<P>> a, vector<Mint<P>> b) {
    if (a.empty() || b.empty()) return {};
    int need = sz(a) + sz(b) - 1;
    if (min(sz(a), sz(b)) <= 32) { vector<Mint<P>> c(need); for (int i = 0; i < sz(a); i++) for (int j = 0; j < sz(b); j++) c[i + j] += a[i] * b[j]; return c; }
    int n = 1; while (n < need) n *= 2;
    a.resize(n); b.resize(n); ntt(a); ntt(b);
    for (int i = 0; i < n; i++) a[i] *= b[i];
    ntt(a, true); a.resize(need); return a;
}
 
using Poly = vector<mint>;
Poly polyMul(const Poly& a, const Poly& b) { return convolution(a, b); }
 
vector<ll> convolutionAnyMod(const vector<ll>& a, const vector<ll>& b, ll m) {   // entries in [0, m), m <= ~1e9, n <= ~1e6
    if (a.empty() || b.empty()) return {};
    constexpr int P1 = 998244353, P2 = 167772161, P3 = 469762049;
    auto run = [&](auto tag) { using Z = decltype(tag); vector<Z> x(all(a)), y(all(b)); return convolution(x, y); };
    auto c1 = run(Mint<P1>()); auto c2 = run(Mint<P2>()); auto c3 = run(Mint<P3>());
    const ll i12 = Mint<P2>(P1).inv().v, i123 = Mint<P3>((ll)P1 * P2 % P3).inv().v;
    vector<ll> res(sz(c1));
    for (int i = 0; i < sz(c1); i++) {                      // Garner: x = x1 + P1 t2 + P1 P2 t3
        ll x1 = c1[i].v, t2 = (c2[i].v - x1 % P2 + P2) % P2 * i12 % P2;
        ll x12 = x1 + (ll)P1 * t2;                          // < P1 P2 < 2^58
        ll t3 = ((c3[i].v - x12 % P3) % P3 + P3) % P3 * i123 % P3;
        res[i] = (ll)(((i128)x12 + (i128)P1 * P2 % m * t3) % m);
    }
    return res;
}

Proof: the modular roots, correctness and the three-prime reconstruction

Roots. $(\mathbb{Z}/p{)}^{\ast }$ is cyclic of order $p-1=c{2}^k$. For a quadratic non-residue $g$ (Euler’s criterion: $g^{(p-1)/2}=-1$) and $j\le k$, $w=g^{(p-1)/2^j}$ satisfies $w^{2^j}=1$ and $w^{2^{j-1}}=g^{(p-1)/2}=-1\ne 1$, so its order is exactly $2^j$: a primitive $2^j$-th root of unity. The table construction keeps roots[k + j] $=w_{2k}^j$: roots[2i] $=$ roots[i] uses $w_{2k}^{2t}=w_k^t$, and roots[2i+1] multiplies by the new primitive $2k$-th root $e$. Correctness. The FFT proof uses only $w^n=1$, $w^{n/2}=-1$ and ${\sum }_k{w}^{jk}=n[j\equiv 0]$ (a geometric series with ratio $\ne 1$ whose $n$-th power is 1), all of which hold for a primitive $n$-th root of unity in any field; the arithmetic is exact, so no rounding is involved. The inverse is the forward transform followed by the index reversal $j\to -j$ and division by $n$ (invertible since $n\mid p-1<p$).

Three primes. Each convolution value $v$ satisfies $0\le v\le n(m-1{)}^2<P_1{P}_2{P}_3$, so $v$ is determined by its residues. Garner’s mixed radix: $x_1=v\mathrm{mod}{P}_1$, $t_2=(v-x_1)P_1^{-1}\mathrm{mod}{P}_2$, $t_3=(v-x_1-P_1{t}_2)(P_1{P}_2{)}^{-1}\mathrm{mod}{P}_3$, and $v=x_1+P_1{t}_2+P_1{P}_2{t}_3$ with each digit in range, so reducing that expression modulo $m$ (with 128-bit intermediates) gives $v\mathrm{mod}m$ (Congruences and CRT). Checked against the quadratic product for random lengths, against all three NTT primes, and with $m=10^9+7$ and $m=2^{30}$.

Optimisation
roots precomputed once per prime (static table above)	the per-level pow of naive code is a large constant
Montgomery / Barrett butterflies, unsigned arithmetic without %	2–3× faster NTT (Fast Modular Multiplication)
one inverse transform for several products (linearity)	e.g. ${\sum }_i{A}_i{B}_i$ in the frequency domain
squaring: one forward transform
middle product / transposed multiplication	half-length transforms in Newton iterations (Power Series)

Uses beyond contests: lattice-based cryptography and homomorphic encryption do all their polynomial ring arithmetic with NTTs; exact big-integer libraries use multi-prime NTT.

Related notes

• FFT (complex FFT, splitting, Karatsuba)
• Power Series (inverse, log, exp, sqrt on top of polyMul)
• Congruences and CRT (Garner)