高速フーリエ変換 (FFT) と多項式乗算

2 つの多項式 $A(x),B(x)$ の積 $C(x)=A(x)B(x)$ は係数の 畳み込み (convolution) $A\otimes B$ であり、素朴計算は $\mathcal{O}(n^2)$。FFT を使うと $\mathcal{O}(n\log n)$ に落とせる。本ヴォルトでは TFHE の実装解析が動機。

鍵となるアイデア

• 係数表現 ⇔ 点値表現 (point-value): $n-1$ 次多項式は $n$ 個の相異なる点で一意に決まる。点値表現では積が点ごとの乗算 $C(x_k)=A(x_k)B(x_k)$ となり $\Theta (n)$。
• 畳み込み定理: フーリエ変換 $\zeta$ の下で畳み込みは要素積になる — $\zeta (f\otimes g)=\zeta (f)\cdot \zeta (g)$。
• 1 の冪根 (roots of unity) ${\omega }_n=e^{2\pi i/m}$ を評価点に「賢く」選ぶ。${\omega }_n^n=1$, ${\omega }_n^{n/2}=-1$ などの対称性を利用。

クーリー–テューキー型 FFT

多項式を偶数次・奇数次に分割し
$A(x)=A_{\mathrm{even}}(x^2)+x{A}_{\mathrm{odd}}(x^2),A(-x)=A_{\mathrm{even}}(x^2)-x{A}_{\mathrm{odd}}(x^2)$
と再帰的に分割統治することで $\mathcal{O}(m\log m)$ を達成する。逆変換（点集合 → 係数）は 補間 (interpolation)。

整数や有限体上では誤差のない 数論変換 (NTT) が用いられる。バタフライ演算で高速化できる変換は他にも多数。

関連: number-theoretic-transform / integer-factorization / _moc-algorithm