Why it matters

NTT gives exact + fast polynomial multiplication. Standard for competitive programming.

Advertisement

The architecture

Choose modulus p = c * 2^k + 1.

Primitive root g.

NTT: FFT with roots of unity in Z_p.

NTT structureModulus pe.g., 998244353Primitive root gfor Z_pButterflysame as FFTCommon p = 998244353 = 119 * 2^23 + 1 with root 3
NTT parameters.
Advertisement

How it works end to end

Butterfly identical to FFT.

Modular inverse for divide by N.

Multi-modulus + CRT for larger results.