数論変換とFFT

離散フーリエ変換を有限体上に持ち込み、整数・多項式乗算を高速化する一連の変換。著者の実装ベンチマーク（Julia）も残されており、暗号（TFHE 等）への応用が背景にある。

DFT と FFT

離散フーリエ変換 (DFT) は 1 の原始 $n$ 乗根 $\omega =e^{2\pi i/n}$ を使う変換で、行列積 $X=Wx$（$W_{jk}={\omega }^{jk}$）で書ける。FFT（高速フーリエ変換） はこれを分割統治で $O(n\log n)$ にする。SPQLIOS のように DFT でなく一般の離散荷重変換 (DWT) を使う実装もある。

NTT（数論変換）

NTT は DFT の有限体への一般化で、環を $\mathbb{Z}/N\mathbb{Z}$ にしたもの。複素数の代わりに法 $N$ の原始根を使う：

1. 入力ベクトル（サイズ $n$）の最大要素より大きい最小モジュラス $M$
2. $N=kn+1$ なる素数 $N\ge M$（ディリクレの定理で存在）
3. 乗法群 ${\mathbb{Z}}_N$ の生成元 $g$ から $\omega \equiv g^k(\mathrm{mod}N)$ を取ると ${\omega }^n\equiv 1$

畳み込みは大きな数や長い多項式の乗算に使え、NTT は Karatsuba 法より漸近的に高速。法は素数でなくてもよく $GF(2^8)$ などでも可。

RNS（剰余数系）

数論変換 / RNS は有限体・中国剰余定理を背景に、互いに素な法の組（例 primes [5,3,2] で $M=30$）で整数を一意表現する。桁上がりが無いため加減乗が各成分独立に高速化でき、補数 $X^c=(M-X)\mathrm{mod}M$ で負数・減算も表せる。

実装メモ

著者は Julia で FFT/NTT/畳み込み/RNS をベンチマーク（有限体ライブラリ）。FFT は $N=512$ 以降で naive を逆転、RNS 係数多項式環まで実装し、NTT は法演算のオーバーヘッドで割り当てが多い、といった実測が残っている。

関連: galois-theory / information-theory / selection-polynomial / _moc-math