NTT

在 FFT 的原理中，我们可以得知，由于单位根 ${\omega }_n=e^{\frac{1}{n}2\pi i}$ 满足两个性质

$${\omega }_{mn}^{mk}={\omega }_n^k,{\omega }_n^k=-{\omega }_n^{k+\frac{n}{2}}$$

于是可以带入到公式 $f(x)=f_e(x^2)+x\cdot f_o(x^2)$ 中得到

$$f({\omega }_n^k)=f_e({\omega }_{\frac{n}{2}}^k)+{\omega }_n^k\cdot f_o({\omega }_{\frac{n}{2}}^k)$$ $$f({\omega }_n^{k+\frac{n}{2}})=f_e({\omega }_{\frac{n}{2}}^k)-{\omega }_n^k\cdot f_o({\omega }_{\frac{n}{2}}^k)$$

从而递归地运算 $f({\omega }_n^0)\dots f({\omega }_n^{n-1})$

因此，通过分治的方式，将多项式在单位根处的求值时间复杂度从 $O(n^2)$ 降低到 $O(n\log n)$。

除了单位复根，