引言

在之前的一篇文章里，我们详细了解了精妙的FFT算法。但它有一个与生俱来的缺点：在复数域上。单位复根的实部和虚部分别是一个正弦及余弦函数，有大量浮点数计算，计算量很大且浮点数运算也会产生较大的误差。

所以我们可不可以把操作对象变成整数呢？快速数论变换（NTT）应运而生。

变换

NTT使用的分治办法，与FTT使用的分治办法完全一致。这意味着，只需在FTT的基础上进行简单修改，即可得到NTT。

原根

对于一个素数 $p$，它的原根 $g$ 是一个整数，使得 $g^1, g^2, \ldots, g^{p-1} \mod p$ 这个序列，能够生成整个乘法群 $Z_p^*$（即 ${1, 2, \ldots, p-1}$ 中的所有元素）。

换句话说，$g$ 的幂模 $p$ 的结果两两不同，且覆盖了 $1$ 到 $p-1$ 的所有整数。

例如，素数 $p = 7$。

• 检查 $g = 3$：$3^1 \equiv 3$, $3^2 \equiv 2$, $3^3 \equiv 6$, $3^4 \equiv 4$, $3^5 \equiv 5$, $3^6 \equiv 1 \mod 7$。
• 序列是 ${3, 2, 6, 4, 5, 1}$，覆盖了 $1-6$ 的所有数。所以 $3$ 是 $7$ 的一个原根。

仿照单位复数根的形式，也将原根的取值看成一个圆，不过这个圆上只有有限个点，每个点表达的是模数的剩余系中的值。

我们令 $\omega_n \equiv g^{(p-1)/n} \mod p$​。这样定义的 $\omega_n$ 满足 $n$ 次单位根的性质：

1. $\omega_n^n \equiv (g^{(p-1)/n})^n \equiv g^{p-1} \equiv 1 \mod p$ （费马小定理）
2. $\omega_n^{n/2} \equiv g^{(p-1)/2} \equiv -1 \mod p$ （因为 $g^{(p-1)/2}$ 是 $1$ 的平方根，只能是 $\pm 1$，而根据原根定义，它不能是 $1$，所以是 $-1$）
3. 序列 $\omega_n^0, \omega_n^1, \ldots, \omega_n^{n-1}$ 是互不相同的。

基于这三点，FFT中的消去引理和折半引理同样成立：

• 消去引理：$\omega_{dn}^{dk} = g^{\frac{p-1}{dn} \cdot dk} = g^{\frac{p-1}{n} \cdot k} = \omega_n^k$
• 折半引理：$\omega_n^{k + n/2} = \omega_n^k \cdot \omega_n^{n/2} = \omega_n^k \cdot (-1) = -\omega_n^k$

完美！现在我们有了一个在整数模 $p$ 域中完美替代复数单位根的元素 $\omega_n$。

有了 $\omega_n$，NTT的实现就和FFT几乎一模一样了。过程依然是：求值（NTT）→ 点乘 → 插值（逆NTT）。

假设我们有一个多项式 $A(x)$，系数在模 $p$ 下，次数小于 $n$（$n$ 是 $2$ 的幂，且 $n \mid p-1$）。

正变换（NTT）

递归分治的过程与FFT完全一致：

1. 将多项式按奇偶索引分成两个子多项式：$A^{[0]}(x)$ 和 $A^{[1]}(x)$。

2. 递归计算 $\operatorname{NTT}(A^{[0]})$ 和 $\operatorname{NTT}(A^{[1]})$。

3. 合并结果：

   对于 $k = 0$ 到 $n/2 - 1$：

   $\operatorname{NTT}(A)[k] = (\operatorname{NTT}(A^{[0]})[k] + \omega_n^k \cdot \operatorname{NTT}(A^{[1]})[k]) \mod p$

   $\operatorname{NTT}(A)[k + n/2] = (\operatorname{NTT}(A^{[0]})[k] - \omega_n^k \cdot \operatorname{NTT}(A^{[1]})[k]) \mod p$

注意：这里的加法、乘法、取模都是在模 $p$ 的整数域中进行的，没有浮点数，没有精度误差！

逆变换（INTT）

逆NTT（INTT）与NTT的差别仅在于：

1. 使用 $\omega_n^{-1} \mod p$ （即 $\omega_n$ 的模逆元）代替 $\omega_n$。
2. 最后结果需要乘以 $n^{-1} \mod p$ （即 $n$ 的模逆元）。

INTT的公式如下： $\operatorname{INTT}(A)[k] = \left( n^{-1} \cdot \sum_{j=0}^{n-1} A[j] \cdot \omega_n^{-kj} \right) \mod p$

在实际代码中，我们通常使用迭代（非递归） 的蝴蝶操作来实现NTT/INTT，以获得更高的效率。

模数 $p$

NTT有一个关键限制：变换长度 $n$ 必须是 $p-1$ 的因子。因为我们需要 $\omega_n = g^{(p-1)/n}$ 是一个整数，这就要求 $n$ 必须能整除 $p-1$。

常见的做法是选择一些形式特殊的素数，使得 $p-1$ 包含一个非常大的 $2$ 的幂因子。

常见NTT模数：

$p = 469762049 = 7 \cdot 2^{26} + 1$，$g = 3$

$p = 998244353 = 7\cdot17 \cdot 2^{23} + 1$，$g = 3$

$p = 1004535809 = 479 \cdot 2^{21} + 1$，$g = 3$

如果问题中的数值非常大，可能需要使用任意模数NTT（通过CRT合并多个不同模数NTT的结果）。

小结

假设我们计算 $A(x) \times B(x) \mod p$，系数在 $[0, p-1]$ 内。

1. 补零：确定长度 $N \geq \operatorname{len}(A) + \operatorname{len}(B) - 1$，且 $N$ 是 $2$ 的幂，并且 $N \mid (p-1)$。
2. 求值（NTT）：计算 $\vec{A’} = \operatorname{NTT}(\vec{A})$，$\vec{B’} = \operatorname{NTT}(\vec{B})$。
3. 点乘：计算 $\vec{C’}[k] = \vec{A’}[k] \cdot \vec{B’}[k] \mod p$，$k=0,1,\ldots,N-1$。
4. 插值（INTT）：计算 $\vec{C} = \operatorname{INTT}(\vec{C’})$。结果 $\vec{C}$ 就是 $A(x) \times B(x) \mod p$ 的系数向量。

数论变换（NTT）完美地将FFT的思想移植到了整数模域中。它通过用原根替代单位根，用模运算替代复数运算，在保留了 $O(n \log n)$ 高效计算能力的同时，提供了绝对精确的结果和更快的速度，使其成为算法竞赛和工程应用中处理大规模整数、多项式卷积问题的首选利器。