快速数论变换 (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。