2015/04/polynomial-multiplication-and-fast-fourier-transform

[utterances-bot]

从多项式乘法到快速傅里叶变换 | Miskcoo’s Space

计算多项式的乘法，或者计算两个大整数的乘法是在计算机中很常见的运算，如果用普通的方法进行，复杂度将会是 $\mathcal O(n^2)$ 的，还有一种分治乘法可以做到 $\mathcal O(n^{\log_23})$ 时间计算（可以看这里）。下面从计算多项式的乘法出发，介绍快速傅里叶变换（Fast Fourier Transform, FFT

https://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform

[waingt]

原根那里写错啦，应该是“如果我们取素数p=k*n+1，并且找到它的原根”