快速数论变换 (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)} = 1 \\ g_n^{n/2} = g^{(p - 1)/2} $$

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

因此应该有 $\pm 1$ 这两种取值。但是由于 $g^{(p-1) / 2} \neq g^{p-1} = 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} = 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。


标签: FFT NTT
创建时间: 2016.08.22
上次修改: 2017.04.10
统计: 1556 字 / 约 6 分钟


数学公式渲染引擎:

KaTeX 渲染效率很高,但是目前 KaTeX 容错性不强,因此使用 KaTeX 时可能会存在一些数学公式无法渲染的情况
先使用 KaTeX 渲染,再使用 MathJax 渲染