快速数论变换 (NTT)
riteme.site

快速数论变换 (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$ 这两种取值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。


  1. $x^2 \equiv 1 \Leftrightarrow x^2 - 1 \equiv 0 \Leftrightarrow (x + 1)(x - 1) \equiv 0 \pmod p$,所以 $p \mid (x + 1)(x - 1)$。由于 $p$ 是质数,所以要么 $p | (x + 1)$,要么 $p | (x - 1)$,分别对应 $x \equiv -1$$x \equiv 1$ 的情况。