快速复数论变换

$\mathbf Z_p$ 上的 NTT 常用于替代 FFT 以提高效率，但是严重依赖模数：是型（如费马质数）时能快速计算，是型（如梅森质数）时却难以进行；对此，Number theoretic transforms to implement fast digital convolution 中的快速复数论变换（complex NTT, CNTT）即 $\mathbf Z_p[\text i]$ 上的 DFT 能解决，但未被重视。

DFT 可逆的条件

交换环上的 DFT 可逆的充要条件是：存在次本原单位根 $\omega$ ，且 $\omega^1-1,\omega^2-1,\cdots,\omega^{n-1}-1$ 可逆。

模高斯整数环 $\mathbf Z_p[\text i]$

为便捷，以下用表示型质数，表示型质数。

是高斯整数 $\mathbf Z[\text i]$ 的素元而不是，因此 $\mathbf Z_{p_-}[\text i]$ 是域而 $\mathbf Z_{p_+}[\text i]$ 不是，但 $\mathbf Z_{p_+}[\text i]$ 上仍可进行 CNTT。

常用模数的单位根

$n=2^{21}$ 时 $p_-=999292927=2^{20}\times953-1$ 的次单位根 $\omega=1+8\text i$ ；

$n=2^{23}$ 时 $p_+=998244353=2^{23}\times119+1$ 的次单位根 $\omega=1+\text i$ ；

$n=2^{16}$ 时 $p_+=65537=2^{16}+1$ 的次单位根 $\omega=4+17573\text i$ 。

务必注意 $\omega^{-1}\equiv\bar\omega$ 不一定成立。

性能和应用

洛谷 P3803 评测记录显示，按照Optimization of number-theoretic transform in programming contests实现的 NTT 及与其同构的 CNTT, FFT 进行 $2^{21}\approx2.1\times10^6$ 长度的变换用时分别约为毫秒。

因此，对于模型质数的卷积问题，CNTT 明显优于三模数 NTT 和拆系数 FFT。

本页面最近更新：2022/6/22 01:18:29，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Saisyc
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

快速复数论变换

DFT 可逆的条件

模 高斯整数环

常用模数的单位根

性能和应用

模高斯整数环 $\mathbf Z_p[\text i]$