数論変換（NTT）

1. 定義と歴史

数論変換（Number Theoretic Transform, NTT）は、複素数体 $\mathbb{C}$ の代わりに有限体 $\mathbb{Z}/p\mathbb{Z}$ ($p$ は素数) 上で定義される離散フーリエ変換である。FFT の数学的構造をそのまま保ちながら、整数の剰余演算のみで完結し、丸め誤差を一切発生させない点が最大の特徴。

歴史的経緯

FFT と NTT の対応関係

図1: NTT は FFT のアルゴリズム構造 (Cooley-Tukey 分割統治、バタフライ演算) をそのまま継承し、演算体だけを複素数から有限体に置き換える。$\omega$ の選び方が違うだけ。

2. 原始根と原始 $N$ 乗根

原始根

素数 $p$ に対し、$\mathbb{Z}/p\mathbb{Z}$ の乗法群 $(\mathbb{Z}/p\mathbb{Z})^* = \{1, 2, \ldots, p-1\}$ は位数 $p - 1$ の巡回群である。この群を生成する元 $g$ を原始根 (primitive root) と呼ぶ。すなわち:

$g$ の位数は $p - 1$ (これより小さい正整数 $k$ で $g^k \equiv 1 \pmod p$ となるものは存在しない)。

原始根の存在と数え方

• 存在: 任意の素数 $p$ に対し原始根は存在する (Gauss, 1801)
• 個数: $\varphi(p - 1)$ 個 ($\varphi$ は Euler の totient 関数)
• 計算: 候補 $g = 2, 3, 5, \ldots$ について、$p - 1$ の各素因数 $q$ に対し $g^{(p-1)/q} \not\equiv 1 \pmod p$ を確認すれば良い (試行 $O(\log p)$ 回程度で見つかる)

原始 $N$ 乗根

$N \mid (p - 1)$ のとき、$\omega = g^{(p-1)/N} \bmod p$ は $\mathbb{Z}/p\mathbb{Z}$ における原始 $N$ 乗根 (primitive $N$-th root of unity) となる:

• $\omega^N \equiv 1 \pmod{p}$ (1 の $N$ 乗根)
• $\omega^k \not\equiv 1 \pmod{p}$ for $0 < k < N$ (原始性)
• $\omega^{N/2} \equiv -1 \pmod p$ (FFT バタフライで使う反復性)

この $\omega$ が FFT における $e^{-j 2\pi / N}$ に対応する。FFT で使う性質:

• 周期性: $\omega^{k+N} = \omega^k$
• 対称性: $\omega^{k + N/2} = -\omega^k$
• 2 乗での縮小: $(\omega^2)$ は原始 $N/2$ 乗根

これらが FFT の分割統治 (Cooley-Tukey) をそのまま使える根拠。

3. NTT の定式化と FFT との対応

変換式

長さ $N$ の整数列 $\{a[n]\}_{n=0}^{N-1}$ (各 $a[n] \in \mathbb{Z}/p\mathbb{Z}$) に対する NTT は:

逆 NTT (INTT) は:

ここで $N^{-1}$ は $N$ の $\bmod p$ における逆元 ($N \cdot N^{-1} \equiv 1 \pmod p$、Fermat の小定理で $N^{-1} = N^{p-2} \bmod p$)、$\omega^{-1}$ は $\omega$ の逆元 ($\omega \cdot \omega^{-1} \equiv 1 \pmod p$、$\omega^{-1} = \omega^{N-1} \bmod p$ で計算)。

行列形式

NTT は線形変換なので、行列で表現できる:

$\Omega_N$ は対称な Vandermonde 型行列で、逆行列は $\Omega_N^{-1} = N^{-1} \cdot \overline{\Omega_N}$ (ここで $\overline{\Omega_N}$ の $(k,n)$ 成分は $\omega^{-kn}$)。これも FFT と同じ構造。

畳み込み定理

性質一覧

4. NTT-friendly 素数

$N = 2^m$ の NTT を行うには $2^m \mid (p - 1)$ が必要 (なぜなら $\omega = g^{(p-1)/N}$ を整数指数で取るため)。NTT-friendly 素数は $p - 1$ が大きな 2 のべき乗を因子にもつ素数を指す:

主要な NTT-friendly 素数

$p$ のビット幅と用途の関係

$p - 1$ の 2-adic 性

$p - 1$ が含む 2 のべき乗の指数 $a$ ($p - 1 = c \cdot 2^a$, $c$ 奇数) を $p$ の 2-adic 値 $\nu_2(p-1) = a$ と呼ぶ。これが NTT で扱える最大長 $N_{\max} = 2^a$ を直接決定する。一般に NTT-friendly 素数を探すには $\nu_2(p - 1)$ が大きい素数を生成する必要がある。

5. 高速モジュラ算術 (Montgomery / Barrett)

NTT の内側ループでは「乗算 + mod $p$」が支配的演算となる。素朴に (a * b) % p を計算すると除算が遅いため、現代の実装では除算を完全に避けるテクニックを使う。

Montgomery 乗算

1985 年 Peter L. Montgomery によるテクニック。$R = 2^k$ ($p < R$、典型的に $k = 32$ または $64$) を選び、すべての値を Montgomery 表現 $\tilde{a} = a R \bmod p$ で保持する。Montgomery 乗算は:

を 除算なしに実行する (Montgomery reduction)。除算の代わりに $R$ での割り算 (シフト) を 1 回行うだけで $\bmod p$ が取れる。

Barrett reduction

1986 年 Paul Barrett 提案。事前に $\mu = \lfloor 2^{2k} / p \rfloor$ を計算しておき、任意の $0 \le x < p^2$ に対し:

を計算 (結果は $x \bmod p$ または $x \bmod p + p$ で、最後に条件付き減算)。Montgomery と違って入力の事前変換が不要だが、定数 $\mu$ は事前計算。

両者の比較

Solinas 素数 (特殊素数)

$p = 2^a - c$ ($c$ 小さい) や $p = 2^a + 2^b - 1$ のような形の素数は、特殊化された mod 計算が可能 (Solinas 1999):

NTT のホットループでは Montgomery + Solinas 素数の組合せで除算系命令を完全排除できる。Mersenne 素数 $2^{31} - 1, 2^{61} - 1$ も Solinas の特殊ケース。

6. アルゴリズム

NTT のアルゴリズムは Cooley-Tukey FFT と同一の構造であり、複素乗算を剰余乗算に置き換えるだけ。in-place の反復版 (decimation-in-time, DIT):

function ntt(a, N, p, omega):
    // ステップ 1: ビット反転順序に並べ替え
    a = bit_reverse_copy(a, N)
    // ステップ 2: 段階的バタフライ
    for s = 1 to log2(N):
        m = 2^s
        wm = power(omega, N/m, p)        // m 乗根 = ω^{N/m}
        for k = 0 to N-1 step m:
            w = 1
            for r = 0 to m/2-1:
                t = (w * a[k + r + m/2]) mod p
                u = a[k + r]
                a[k + r]       = (u + t) mod p
                a[k + r + m/2] = (u - t + p) mod p
                w = (w * wm) mod p
    return a

1 反復のコスト

• バタフライ演算数: $\tfrac{N}{2} \log_2 N$ (FFT と同じ)
• 1 バタフライあたり: 1 乗算 + 2 加算 (mod $p$)
• 合計: $O(N \log N)$ の mod 乗算

Montgomery 化した版

実用実装では、すべての値を Montgomery 表現で保持し、バタフライ内の w * a[...] を Montgomery 乗算で実行する。$\omega, \omega^2, \ldots$ も事前に Montgomery 表現で計算しておく:

// Pre-compute Montgomery-form roots
omega_mont = (omega * R) mod p
wm_table[s] = (omega^{N/(2^s)} * R) mod p  for s = 1..log2(N)

// Hot inner loop (no division at all)
for r = 0 to m/2-1:
    t = MontMul(w, a[k+r+m/2])
    a[k+r+m/2] = SubMod(a[k+r], t)
    a[k+r]     = AddMod(a[k+r], t)
    w = MontMul(w, wm_table[s])

並列化

• SIMD: AVX-512 の VPMULQ + Montgomery reduction で 8 並列 mod 乗算が可能
• GPU: cuFHE 等で warp-level での実装が公開されている
• マルチコア: バタフライ段の外側ループを OpenMP 等で並列化、$O(\log N)$ の同期段

逆 NTT は $\omega$ を $\omega^{-1}$ に置き換え、最後に $N^{-1} \bmod p$ を全要素に乗じる (NTT と完全に同型)。

7. negacyclic NTT と $\mathbb{Z}_p[x]/(x^N+1)$

標準 NTT は循環畳み込み ($\bmod\, x^N - 1$) を計算する。しかし格子暗号 (Ring-LWE) では反循環畳み込み ($\bmod\, x^N + 1$) が必要。これを直接 NTT で計算する手法が negacyclic NTT。

反循環畳み込みとは

多項式環 $\mathbb{Z}_p[x] / (x^N + 1)$ では $x^N \equiv -1$ なので、係数のシフトで符号が反転する:

これにより、$x^N + 1$ で割った余りを計算するためには通常の畳み込みでは不適切。

negacyclic NTT の構成

原始 $2N$ 乗根 $\psi$ を用意し ($\psi^N \equiv -1 \pmod p$、つまり $2N \mid (p-1)$ が必要)、係数を事前に

と「ねじって」から長さ $N$ の通常 NTT を適用する。畳み込み後に逆ねじり $\psi^{-n}$ を掛けると、$\mathbb{Z}_p[x] / (x^N + 1)$ 上の積が得られる。

この前処理 (ねじりとほどき) は $O(N)$ で、本体 NTT $O(N \log N)$ と比べて無視できる。

8. 多項式乗算と CRT 合成

次数 $n$ と $m$ の多項式 $f(x), g(x)$ の積 $h(x) = f(x) \cdot g(x)$ を計算する。$h$ の次数は $n + m$、係数は $n + m + 1$ 個。

計算量は $O(N \log N)$ であり、直接計算の $O(nm)$ と比べて大幅に高速化される。

係数がモジュロ範囲を超える場合: CRT 合成

係数 $c_i$ が大きくなり 1 つの素数 $p$ では $c_i \bmod p$ が衝突する可能性があるとき、複数の NTT-friendly 素数 $p_1, p_2, p_3$ で並列に NTT 乗算を行い、中国の剰余定理 (CRT) で合成する:

1. $p_1 = 998244353$, $p_2 = 985661441$, $p_3 = 754974721$ などで各々 NTT 乗算
2. 各係数 $c_i$ について $c_i \bmod p_j$ ($j = 1, 2, 3$) を取得
3. CRT で $c_i \bmod (p_1 p_2 p_3)$ を復元 (Garner アルゴリズムで段階的に)

Garner アルゴリズム

3 素数の場合の効率的な CRT 復元:

// 入力: x mod p1, x mod p2, x mod p3
// 出力: x mod (p1*p2*p3)
inv_12 = modinv(p1, p2)
inv_123 = modinv(p1*p2 mod p3, p3)
v1 = x_mod_p1
v2 = (x_mod_p2 - v1) * inv_12 mod p2
v3 = ((x_mod_p3 - v1) - v2*p1) * inv_123 mod p3
return v1 + v2*p1 + v3*p1*p2

sangi での実装

sangi の 5-smooth NTT は $N = 2^a 3^b 5^c$ のサイズで radix-3/5 バタフライを実装している。これにより NTT 利用域が標準実装の $N = 2^k$ の場合より広がる (50% → 80% 以上)。Cooley-Tukey の混合基数版を NTT に応用した形。

9. 多倍長整数乗算 (Schönhage-Strassen)

$d$ 桁の整数 $A, B$ の乗算を NTT で行うには:

1. 各整数を基数 $B$ (例: $B = 2^{16}$ または $B = 10^4$) の係数列として表現する (長さ $L = \lceil d / \log_B \rceil$ の多項式と見なす)
2. NTT で多項式乗算 → $A \cdot B$ の係数 (まだ $B$ を超える「桁」を含む)
3. 繰り上がり処理: 各係数 $c_i$ を $c_i \bmod B$ + $\lfloor c_i / B \rfloor$ を次に繰り越し

計算量は $O(d \log d \log \log d)$ (Schönhage-Strassen)、または現代の改良で $O(d \log d \cdot 2^{O(\log^* d)})$ (Fürer 2007)、最終的に $O(d \log d)$ (Harvey-van der Hoeven 2019)。筆算 $O(d^2)$、Karatsuba $O(d^{1.585})$、Toom-Cook $O(d^{1.465})$ と比べて漸近的に高速。

Schönhage-Strassen アルゴリズム

1971 年提案の古典的な NTT 整数乗算法:

1. 分割: $A, B$ を $K$ 個のブロックに分け、長さ $L = 2K$ の多項式と見なす
2. $\bmod (2^M + 1)$ で計算: 各係数は $M$ ビット範囲。$M = O(d^{1/2})$ 程度を選ぶ
3. 長さ $L$ の NTT: $\omega$ として $2^{M/L}$ を取る (これが原始 $L$ 乗根になる)
4. 係数乗算: 各係数の積は $M$ ビット同士なので、再帰的に同じアルゴリズムを適用 ($\log \log d$ 段の再帰)
5. 逆 NTT + carrying

$\bmod (2^M + 1)$ NTT

有限体 $\mathbb{Z}_p$ ではなく、剰余環 $\mathbb{Z}/(2^M + 1)\mathbb{Z}$ で NTT を実行する変種。$2$ が原始 $2M$ 乗根になる ($2^{2M} = (2^M)^2 \equiv (-1)^2 = 1$、原始性も成立) ため、$\omega = 2^{(2M)/L} = 2^{2M/L}$ で乗算 = シフト演算で済む。これが Schönhage-Strassen の核心的高速化。

現代のライブラリ実装

典型的に「小さい場合は二次法 (筆算/Karatsuba)、中規模で Toom-Cook、大規模で NTT」のハイブリッド戦略を取る。クロスオーバー点はハードウェアと実装次第。

10. 格子暗号と PQC への応用

NIST が 2024 年に標準化した 耐量子計算機暗号 (PQC) の中核アルゴリズム CRYSTALS-Kyber と CRYSTALS-Dilithium は、いずれも NTT で多項式環演算を高速化している。

Ring-LWE 問題と多項式演算

Ring-Learning With Errors (RLWE) 問題は、多項式環 $R = \mathbb{Z}_p[x] / (x^N + 1)$ 上で:

から秘密 $s$ を推定する困難性に基づく。$a, s, e \in R$ で多項式は $N - 1$ 次。実用ではかなり大きな多項式環 ($N = 256, 512, 1024$) を使うため、$a \cdot s$ の計算が支配的コスト → NTT で $O(N \log N)$ 化する。

主要 PQC スキーム

準同型暗号 (FHE) での NTT

BFV, BGV, CKKS などの完全準同型暗号 (FHE) も同じ多項式環構造を使い、NTT が暗号化・復号化・乗算の全段階で支配的演算となる。Microsoft SEAL, IBM HElib, Lattigo (Go) などのライブラリで標準実装。

サイドチャネル攻撃と一定時間実装

暗号用途の NTT は一定時間 (constant-time) 実装が必須。分岐や非定数アクセスがあるとタイミング攻撃で秘密値が漏洩する。Montgomery 乗算の最後の条件付き減算はマスク化 (常に減算してマスクで選択) する。

11. 競技プログラミングでの応用

競プロでは「mod $p$ の下での畳み込み」が頻出問題で、NTT は必須テクニック。

典型問題

• 多項式乗算: $\bmod 998244353$ の下で長さ $10^5$ の多項式の積
• 畳み込みカウント: $c_k = \sum_{i+j=k} a_i b_j$ の各値
• サブセット和の数: 母関数による組合せ数え上げ
• 形式的冪級数: $\bmod x^n$ での $\exp, \log, \sqrt{}, \mathrm{inv}$ など (Newton 反復 + NTT)

任意 mod 畳み込み

競プロでは入力 mod が 998244353 でない場合 ($10^9 + 7$ など) もある。この場合 3 つの NTT-friendly 素数 $p_1, p_2, p_3$ で並列に NTT し Garner で合成、最後に目標 mod に変換するのが標準。

• $p_1 = 998244353$, $p_2 = 985661441$, $p_3 = 754974721$ (Garner 用 3 素数)
• 合計コスト: 3 倍の NTT + Garner 復元 $O(N)$ → 標準 NTT の約 3-4 倍

AtCoder Library の convolution

AtCoder Library (ACL) は競プロ用 C++ ライブラリで、atcoder::convolution<Mod> が NTT による畳み込みを提供。$\mathrm{Mod} = 998244353$ で最高速、それ以外でも自動で適切な戦略を選択する。

12. NTT vs FFT 比較

使い分けの基準

• 連続値・近似で十分: FFT (信号処理、PDE 解法)
• 厳密整数結果が必須: NTT (整数乗算、暗号、競プロ)
• $N$ が任意で 2-adic 制約が嫌: FFT + Bluestein フォールバック
• $N$ が固定で速度最優先: NTT (暗号、Kyber/Dilithium)

13. 計算例

例 1: $p = 5$, $N = 4$ の最小 NTT

例 2: $\bmod 998244353$ の多項式乗算

例 3: Kyber 多項式環での演算 ($p = 3329, N = 256$)

// 入力多項式 a, b を Montgomery 表現に変換
// negacyclic NTT 前処理: a'[i] = ψ^i * a[i]
// 標準 NTT 256 点
// 要素ごと乗算
// 逆 NTT 256 点
// 後処理: a[i] = ψ^{-i} * a'[i]

14. よくある質問

15. 参考資料

原典・主要論文

• J. M. Pollard, "The fast Fourier transform in a finite field," Math. Comp., 25(114), pp. 365–374, 1971. (NTT の数学的原型)
• A. Schönhage & V. Strassen, "Schnelle Multiplikation großer Zahlen," Computing, 7, pp. 281–292, 1971. (NTT 整数乗算)
• P. L. Montgomery, "Modular multiplication without trial division," Math. Comp., 44(170), pp. 519–521, 1985.
• D. Harvey & J. van der Hoeven, "Integer multiplication in time $O(n \log n)$," Annals of Math., 193(2), pp. 563–617, 2021.
• V. Lyubashevsky, C. Peikert & O. Regev, "On ideal lattices and learning with errors over rings," J. ACM, 60(6), 2013. (Ring-LWE)

書籍

• J. von zur Gathen & J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
• D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997.
• R. E. Blahut, Fast Algorithms for Signal Processing, Cambridge University Press, 2010.
• D. J. Bernstein, J. Buchmann & E. Dahmen (eds.), Post-Quantum Cryptography, Springer, 2009.

sangi での実装 (相互リンク)

• sangi — 整数乗算アルゴリズム — Karatsuba → Toom-3/4/6/8 → 5-smooth NTT のハイブリッド戦略と閾値
• sangi — FFT API — 多倍長整数乗算で使われる NTT/FFT モジュールの C++ インターフェース

関連章

• 離散フーリエ・FFT (章ハブ)
• 離散フーリエ変換 (DFT) — NTT が計算する対象
• 高速フーリエ変換 (FFT) — 全体俯瞰
• Cooley-Tukey 型 FFT — NTT のアルゴリズム構造の起源
• Bluestein FFT — 任意長 DFT、有限体 Bluestein もある

オンライン資料

• Wikipedia: Number-theoretic transform
• Wikipedia: Schönhage-Strassen algorithm
• AtCoder Library — Convolution — 競プロ標準実装
• CRYSTALS Suite (Kyber/Dilithium) — PQC 標準の NTT 実装
• FLINT — 計算機代数システムでの NTT 実装