.png)
$\zeta_n \coloneqq \cos(2\pi / n) + i\sin(2\pi/n)$ （ $1$ の原始 $n$ 乗根）
任意の $n,k$ について $\zeta_n^k = \cos(2k\pi / n) + i\sin(2k\pi/n)$ は $O(1)$ で求められるとする．
以下の図のように $\zeta_n^0, \zeta_n^1,\dots,\zeta_n^{n-1}$ は複素数平面では単位円上に等間隔で反時計回りに並ぶ．
$n=8$ の時の例 単位円上に等間隔で並んでいる
以下では $n-1$ 次多項式 $a_0x^0+\cdots+a_{n-1}x^{n-1}$ のことを $n$ 項多項式と書く． ただしこれは $a_{n-1}\neq 0$ であることを仮定しない． たとえば ****$1 + 3x + x^3$ は $4$ 項多項式であるが，同時に $5$ 項多項式や $6$ 項多項式でもある． 見た目の項数は三つだが $3$ 項多項式とは呼ばないことに注意．（注目するのは最大次数）
多項式 $f(x),g(x)$ の積 $fg(x)$ を求める． 数列 $\bm{a},\bm{b}$ に対して $c_k = \sum_{i+j=k} a_ib_j$ を満たす数列 $\bm{c}$ を求めると思っても良い．
愚直にやると $f,g$ の項数をそれぞれ $n,m$ として $\Theta(nm)$ 時間．
理解が比較的簡単な再帰アルゴリズムを紹介する． 再帰なので定数倍は遅いが，計算量は $fg(x)$ が $N$ 項多項式として $\Theta(N\log N)$ 時間．
$N = n+m-1$ であり，ざっくり $\max\{n,m\}$ 程度である． したがって $n=m$ の時愚直は $\Theta(N^2)$ であり， $\Theta(N\log N)$ より遅い．
事実1
$n$ 項多項式 $f(x)$ は相異なる $n$ 点 $x_0,\dots,x_{n-1}$ の値 $f(x_0),\dots,f(x_{n-1})$ から復元可能． （$f(x_1),\dots,f(x_n)$ の値を指定した場合条件を満たす $n$ 項多項式は一意に定まるということ）
事実2
$fg(x_i) = f(x_i) g(x_i)$