快速数论变换


简介

数论变换(number-theoretic transform, NTT)是离散傅里叶变换(DFT)在数论基础上的实现;快速数论变换(fast number-theoretic transform, FNTT)是

快速傅里叶变换(FFT)在数论基础上的实现。

数论变换 是一种计算卷积(convolution)的快速算法。最常用算法就包括了前文提到的快速傅里叶变换。然而快速傅立叶变换具有一些实现上的缺点,举例来说,资料向量必须乘上复数系数的矩阵加以处理,而且每个复数系数的实部和虚部是一个正弦及余弦函数,因此大部分的系数都是浮点数,也就是说,必须做复数而且是浮点数的运算,因此计算量会比较大,而且浮点数运算产生的误差会比较大。

NTT 解决的是多项式乘法带模数的情况,可以说有些受模数的限制,数也比较大。目前最常见的模数是 998244353。

前置知识

学习数论变换需要前置知识:离散傅里叶变换、生成子群、

原根、离散对数。相关知识可以在对应页面中学习,此处不再赘述。

定义

数论变换

在数学中,NTT 是关于任意

上的离散傅立叶变换(DFT)。在有限域的情况下,通常称为数论变换 (NTT)。

数论变换(NTT)是通过将离散傅立叶变换化为 ,整数模质数 。这是一个 有限域,只要 可除 ,就存在本原 次方根,所以我们有 对于 正整数 。具体来说,对于质数 ,原根 满足 , 将 看做 的等价,则其满足相似的性质,比如

因为这里涉及到数论变化,所以 (为了区分 FFT 中的 ,我们把这里的 称为 )可以比 FFT 中的 大,但是只要把 看做这里的 就行了,能够避免大小问题。

常见的有:

就是 的等价

迭代到长度 ,或者

快速数论变换

快速数论变换(FNTT)是数论变换(NTT)增加分治操作之后的快速算法。

快速数论变换使用的分治办法,与快速傅里叶变换使用的分治办法完全一致。这意味着,只需在快速傅里叶变换的代码基础上进行简单修改,即可得到快速数论变换的代码。

在算法竞赛中常提到的 NTT 一词,往往实际指的是快速数论变换,一般默认“数论变换”是指“快速数论变换”。

这样简写的逻辑与快速傅里叶变换相似。事实上,“快速傅里叶变换”(FFT)一词指的是“快速离散傅里叶变换”(FDFT),但由于“快速”只能作用于离散,甚至是本原单位根阶数为 的幂的特殊情形,不能作用于连续,因此“离散”一词被省略掉,FDFT 变为 FFT,即 FFT 永远指的是特殊的离散情形。

数论变换或快速数论变换是在取模意义下进行的操作,不存在连续的情形,永远是离散的,自然也无需提到离散一词。

在算法领域,不进行提速的操作是无意义的。在快速傅里叶变换中介绍 DFT 一词,是因为 DFT 在信号处理、图像处理领域也有其他的具体应用,同时 DFT 也是 FFT 的原理或前置知识。

在不引起混淆的情形下,常用 NTT 来代指 FNTT。为了不引起下文进一步介绍的混淆,下文的 NTT 与 FNTT 两个词进行了分离。

DFT、FFT、NTT、FNTT 的具体关系是:

  • 在 DFT 与 NTT 的基础上,增加分治操作,得到 FFT 与 FNTT。分治操作的办法与原理,可以参见快速傅里叶变换一文。

  • 在 DFT 与 FFT 的基础上,将复数加法与复数乘法替换为模 意义下的加法和乘法,一般大小限制在 之间;将本原单位根改为模 意义下的相同阶数的本原单位根,阶数为 的幂,即可得到 NTT 与 FNTT。

由于替换的运算只涉及加法和乘法,因此 DFT、FFT、NTT、FNTT 拥有相同的原理,均在满足加法与乘法的环上进行,无需域上满足除法运算的更加严格的条件。

事实上,只要拥有原根,即群论中的生成元,该模数下的 NTT 或 FNTT 即可进行。考虑到模数为 的情形太小,不具有实际意义,对于奇素数 和正整数 ,只要给出模数为 的原根 ,采用同样的办法,则 NTT 或 FNTT 仍然可以进行。

模板

下面是一个大数相乘的模板,参考来源

参考资料与拓展阅读

贡献者:@Yufan@Tifa@Great-designer@Shuzhou@Ir1d@Danni@tigerruanyifan@mgt@ranwen@Omega癸@GeZiyue@ouuan@Sshwy@Xeonacid@Henry@TrisolarisHD

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组