龙岩网站建设设计制作,高端品牌包包都有哪些,网站建设管理指导意见,湘潭做网站公司选择封象网做网站公司什么是NTT#xff1f;
数论变换#xff08;number-theoretic transform, NTT#xff09;是离散傅里叶变换#xff08;DFT#xff09;在数论基础上的实现。 NTT是一种计算卷积的快速算法#xff0c;FFT也是其中一种。
但是FFT具有一些实现上的缺点#xff0c;举例来说
数论变换number-theoretic transform, NTT是离散傅里叶变换DFT在数论基础上的实现。 NTT是一种计算卷积的快速算法FFT也是其中一种。
但是FFT具有一些实现上的缺点举例来说向量必须乘上复数系数的矩阵进行处理而且每个复数系数的实部和虚部是一个正弦及余弦函数因此大部分的系数都是浮点数也就是说必须做浮点复数运算计算量会比较大并且浮点数运算产生的误差会比较大。
NTT解决的是多项式乘法带模数的情况受到模数的限制数也比较大。 在数学中NTT 是关于任意环上的DFT。在有限域的情况下通常称为数论变换即NTT。
原根
FFT的实现是找单位圆上的 n n n个点 ω n 0 , ω n 1 , … , ω n n \omega_n^0, \omega_n^1, \dots, \omega_n^n ωn0,ωn1,…,ωnn称为单位根 然后对这些点进行FFT。因此对于NTT我们需要在取模域上找到和这个点等价的数。为了找到这 n n n个等价的数我们要使用原根。
令 n n n为大于1的2的幂 p p p为质数且 n ∣ ( p − 1 ) n|(p-1) n∣(p−1)即 n n n整除 p − 1 p-1 p−1 则存在本原 n n n次方根。对于质数 p q n 1 pqn1 pqn1模 p p p意义下的原根 g g g满足 g q n 1 ( m o d p ) g^{qn}1 (\mod p) gqn1(modp)将 g n g q ( m o d p ) g p − 1 n ( m o d p ) g_ng^q (\mod p)g^{{p-1}\over n} (\mod p) gngq(modp)gnp−1(modp)看作 ω n \omega_n ωn的等价。
于是原根 g n g_n gn和单位根 ω n \omega_n ωn满足相似的性质
原根和单位根的等价性 g n g p − 1 n g_ng^{{p-1}\over n} gngnp−1
于是 g n n g n ⋅ p − 1 n g p − 1 g_n^ng^{n \cdot {p-1\over n}}g^{p-1} gnngn⋅np−1gp−1 g n n 2 g p − 1 2 g_n^{n\over 2}g^{p-1\over 2} gn2ng2p−1 g a n a k g a k ( p − 1 ) a n g k ( p − 1 ) n g n k 【对应单位根消去引理】 g_{an}^{ak}g^{\frac{ak(p-1)}{an}}g^{\frac{k(p-1)}{n}}g_n^k【对应单位根消去引理】 ganakganak(p−1)gnk(p−1)gnk【对应单位根消去引理】
可以得到 g n n ≡ 1 ( m o d p ) 【对应单位根 ω n n ≡ 1 】 g_n^n \equiv 1 (\mod p) 【对应单位根\omega_n^n\equiv 1】 gnn≡1(modp)【对应单位根ωnn≡1】 g n n 2 ≡ − 1 ( m o d p ) 【对应单位根 ω n n 2 ≡ − 1 】 g_n^{n\over 2} \equiv -1 (\mod p)【对应单位根\omega_n^{n\over 2}\equiv -1】 gn2n≡−1(modp)【对应单位根ωn2n≡−1】 g n k n 2 g n k ⋅ g n n 2 − g n k ( m o d p ) 【对应单位根折半引理】 g_n^{k{n\over 2}}g_n^{k}\cdot g_n^{n\over 2}-g_n^{k} (\mod p)【对应单位根折半引理】 gnk2ngnk⋅gn2n−gnk(modp)【对应单位根折半引理】 ( g n k n 2 ) 2 g n 2 k n g n 2 k ⋅ g n n g n 2 k ( m o d p ) (g_n^{k{n\over 2}})^2g_n^{2kn}g_n^{2k}\cdot g_n^ng_n^{2k} (\mod p) (gnk2n)2gn2kngn2k⋅gnngn2k(modp)
我们发现单位根具有的性质原根都有所以我们将 g n k g_n^k gnk和 g n k n 2 g_n^{k{n\over 2}} gnk2n代入本质上和将 ω n k \omega_n^k ωnk和 ω n k n 2 \omega_n^{k{n\over 2}} ωnk2n代入并无二异
在INTT中乘单位根的共轭复数的操作也就会相应地变为乘原根在模意义下的逆元。
常见的模数和原根如下 p 1004535809 479 × 2 21 1 , g 3 p 998244353 7 × 17 × 2 23 1 , g 3 p1004535809479\times 2^{21}1, g3 \\ p 9982443537\times 17\times2^{23}1, g3 p1004535809479×2211,g3p9982443537×17×2231,g3
快速数论变换FNTT
简而言之FNTT是NTT增加分治操作之后的快速算法也是FFT在数论基础上的实现。FNTT使用的分治办法与FFT使用的分治办法完全一致。
DFT、FFT、NTT、FNTT的关系
在 DFT与NTT的基础上增加分治操作得到FFT与FNTT。分治操作同FFT一致。在DFT与FFT的基础上将复数加法与复数乘法替换为模 p p p意义下的加法和乘法一般大小限制在0到 p − 1 p-1 p−1之间将本原单位根改为模 p p p意义下的相同阶数的本原单位根阶数为2的幂即可得到NTT与FNTT。
一大堆参考资料
快速数论变换NTT超详解OI Wiki 快速数论变换快速数论变换NTT快速傅立叶变换FFT学习笔记
