数論変換

Last updated Oct 23, 2022 Edit Source

複素数上のFFTを有限体上に取り替えたのがNTT。乗法群の位数が大きな2のべき乗を持っていると精度を落とさずに計算できて嬉しい。

$O(N\log{N})$