快速数论变换 (NTT)

之前写了一篇关于多项式算法的博客，提到了快速傅立叶变换 (FFT)。
快速傅立叶变换中使用了单位复数根来进行采样与插值，快速数论变换和这是类似的，只不过使用的是原根。

原根的性质

为了方便，假设下面所有的 $n$ 都是大于 $1$ 的 $2$ 的幂，我们设：

$$ g_n = g^{(p-1) / n} $$

其中 $p$ 是素数并且 $n \mid (p-1)$，另外 $g$ 是模 $p$ 意义下的原根。
考虑下单位复数根为什能做到 $\Theta(n \log n)$ 的时间复杂度，是因为它具有下面的性质：

$$ \omega_n^n = 1 \\ \omega_n^{n/2} = -1$$

对原根而言：

$$ g_n^n = g^{n(p-1) / n} = g^{p-1} = g^{\varphi(p)} \equiv 1 \pmod p \\ g_n^{n/2} = g^{(p - 1)/2} $$

而：

$$ (g^{(p - 1)/2})^2 \equiv g^{p - 1} \equiv 1 \pmod{p} $$

方程 $x^2 \equiv 1 \pmod p$ 在 $p$ 为素数时只有 $\pm 1$ 这两种取值¹。但是由于 $g$ 是原根，所以 $g^{(p-1) / 2} \not\equiv g^{p-1} \equiv 1$，故其为 $-1$。

$$ \omega_{dn}^{dk} = \omega_n^k $$

原根也可以：

$$ g_{dn}^{dk} = g^{dk(p-1) / dn} = g^{k(p-1) / n} = g_n^k $$

(折半引理)

$$ \{(\omega_n^k)^2\} = \{\omega_{n/2}^k\} $$

原根依然可以。根据上面的结论，我们有：

$$ (g_n^{k})^2 = g_{n}^{2k} = g_{n/2}^k \\ (g_n^{k+n/2})^2 = g_n^{2k+n} \equiv g_n^{2k} = g_{n/2}^k $$

因此，单位复数根该有的性质原根居然都有！

NTT 算法

从上面的讨论中我们知道，将你的 FFT 代码中的单位复数根换成 $g_n^k$，就是 NTT。注意到处取模。
逆 FFT 变换时需要除以 $n$，在模 $p$ 意义下记住是使用逆元。
NTT 的总复杂度与 FFT 一致，是 $\Theta(n \log n)$。

最后还剩下一个问题：$p$ 和 $g$ 该怎么办。
在 FFT 中，为了方便处理，$n$ 一般都是选定了一个 $2$ 的幂。因此，对于 $p$，我们只需要选出一个 $p-1$ 中含有 $2$ 的幂的因子的素数，并且这个 $2$ 的幂要大于 $n$。通常选择形如 $a\cdot 2^k + 1$ 的素数。
为了方便，通常选定：

$$ p = 1004535809 = 479 \times 2^{21} + 1 $$

它的最小正原根是 $3$。

另外一个是著名的 UOJ 模数 $998244353 = 2^{23} \times 7 \times 17 + 1$，最小正原根也是 $3$。
使用快速数论变换的好处就是避免了浮点数精度误差。当输入系数都是整型的时候最好优先考虑 NTT。