NTT ,快速数论变换,功能与 FFT 完全一致,用来求多项式卷积。
NTT 优点在于常数稍微小一点,没有精度误差。
但是 NTT 系数必须是取模意义下的整数,且对模数有特殊要求。

FFT 的单位根

建议前置 FFT

FFT 可以分治优化复杂度的原因是用到了单位根的如下性质:
$$ W_{2n}^{2k} = W_n^k $$
$$ W_n^n = 1 $$
$$ W_n^{k + n/2} + W_n^k = 0 $$

可是用单位根做 FFT ,需要用到复数和浮点数,常数大而且有精度误差。
还有别的数有这样的性质来替换单位根吗?
遗憾的是,可以证明复数域下只有单位根有这样的性质。

取模

实际计算多项式卷积时,常常要求对系数取模以避免不必要的麻烦。
那么这时候系数实际上是在模意义下的, FFT 将它转到复数域上运算,似乎没有必要。
模意义下什么数可以有单位根那样的性质?
有的,那就是原根。

原根

对于某些模数 P ,模 P 意义下的原根 g 满足:
对任意 $ 0 \leq k \leq P – 2 $ , $ g^k $ 互不相同。
有些模数可能不存在原根,这里先假设模数都有原根。

假设系数是模 P 意义下的,P 是形如 $ 2^k + 1 $ 的质数,其原根为 g ,
设 $ G_n = g^{\frac{P-1}{n}} mod P $ ,其中 n 是小于 P 的 2 的整次幂 。
那么在模 P 意义下, G 满足:

$$ G_{2n}^{2k} = G_n^k $$

由 G 定义可证:
$ G_{2n}^{2k} = g^{\frac{P-1}{2n}2k} = g^{\frac{P-1}{n}k} = G_n^k$

$$ G_n^n = 1 $$

由 G 定义可得:
$ G_n^n = g^{\frac{P-1}{n}n} = g^{P-1} $
由费马小定理:
$ G_n^n = g^{P-1} = 1 $

$$ G_n^{k + n/2} + G_n^k = 0 $$

有第一条性质可得:
$ G_n^{n/2} = G_2^1 = g^{\frac{P-1}{2}} $
因为 $ (g^{\frac{P-1}{2}})^2 = g^{P-1} = 1 $
根据原根的性质:
$ g^{\frac{P-1}{2}} \neq g^{P-1} $
那么 $ g^{\frac{P-1}{2}} = -1 $ (即 P – 1)。
那么可以证得:
$ G_n^{k + n/2} = G_n^k G_n^{n/2} = G_n^k(-1) $
于是 $ G_n^{k + n/2} + G_n^k = 0 $

NTT

于是 NTT 的算法思路就呼之欲出了:把 $ W_n $ 全部替换为 $ G_n $ 即可。
这样就可以算出模 P 意义下的多项式卷积了。
其中 n 必须是 2 的整次幂,不足的补零即可。

现在唯一的问题是,模数 P 要满足什么条件,以及如何求模 P 意义下的原根 g 。
然而我并不想深入展开,大多数情况下模数都是 998244353 ,其原根为 3 。
一般 NTT 只会用这个模数,不会有毒瘤出题人卡这个模数的(我不对这句话负责)。

分类: 多项式

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: