【算法】快速数论变换(NTT)初探
【简介】 快速傅里叶变换(FFT)运用了单位复根的性质减少了运算，但是每个复数系数的实部和虚部是一个余弦和正弦函数，因此系数都是浮点数，而浮点数的运算速度较慢且可能产生误差等精度问题，因此提出了 以数论为基础的具有循环卷积性质的快速数论变换(NTT)。 在FFT中，通过 n n 次单位复根即 ω n = 1 ω n = 1 的 ω ω 来运算，而对于NTT来说，则是运用了素数的原根来运算。 【原根】 【定义】 对于两个正整数 a , m a , m 满足 g c d ( a , m ) = 1 g c d ( a , m ) = 1 ，由欧拉定理可知，存在正整数 d ≤ m − 1 d ≤ m − 1 ，如 d = φ ( m ) d = φ ( m ) ，使得 a d ≡ 1 ( m o d m ) a d ≡ 1 ( m o d m ) 。 因此，在 g c d ( a , m ) = 1 g c d ( a , m ) = 1 时，定义 a a 对模 m m 的指数 δ m ( a ) δ m ( a ) 为使 a d ≡ 1 ( m o d m ) a d ≡ 1 ( m o d m ) 成立的最小正整数 d d 。若 δ m ( a ) = φ ( m ) δ m ( a ) = φ ( m ) ，则称 a a 是模 m m 的原根。 【性质/定义2】 若一个数 g g 是对于 P P 的原根，那么 g i m o d P , 1 ≤ i < P g i m o d P , 1 ≤ i < P 的结果互不相同。 【求原根方法】 对质数 P − 1 P − 1 分解质因数得到不同的质因子 p 1 , p 2 , p 3 , . . . , p n p 1 , p 2 , p 3 , . . . , p n ，对于任何 2 ≤ a ≤ P − 1 2 ≤ a ≤ P − 1 ，判定 a a 是否为 P P 的原根，只需要检验 a P − 1 p 1 , a P − 1 p 2 , . . . , a P − 1 p n a P − 1 p 1 , a P − 1 p 2 ,...