快速复数论变换

上的 NTT 常用于替代 FFT 以提高效率,但是严重依赖模数: 型(如费马质数)时能快速计算,是 型(如梅森质数)时却难以进行;对此,Number theoretic transforms to implement fast digital convolution 中的快速复数论变换(complex NTT, CNTT)即 上的 DFT 能解决,但未被重视。

DFT 可逆的条件

交换环 上的 DFT 可逆的充要条件是:存在 次本原单位根 ,且 可逆。

高斯整数环

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

是高斯整数 的素元而 不是,因此 是域而 不是,但 上仍可进行 CNTT。

常用模数的单位根

次单位根

次单位根

次单位根

务必注意 不一定成立。

性能和应用

洛谷 P3803 评测记录 显示,按照Optimization of number-theoretic transform in programming contests实现的 NTT 及与其同构的 CNTT, FFT 进行 长度的变换用时分别约为 毫秒。

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