NTT は FFT とどう違いますか？

FFT は複素数体上で離散フーリエ変換を行い、浮動小数点演算による丸め誤差を伴う。NTT は有限体 (剰余環) 上で同じバタフライ構造を実行するため、整数のままで誤差ゼロで畳み込みを計算できる。多倍長整数乗算など正確性が要る場面で NTT が選ばれる。

NTT-friendly 素数とは何ですか？

p − 1 が大きな 2 の冪で割り切れる素数。p − 1 = c · 2^k の形なら最大 2^k 点の NTT が可能。sangi の prime1, prime2, prime3 はそれぞれ 30·2^47 + 1、345·2^47 + 1、420·2^47 + 1 という p ≈ 2^52 の素数で、いずれも 2^47 点までの NTT に対応する。3 素数 CRT で結合すると有効ビット幅は約 156 bit に達する。

Schönhage-Strassen NTT は通常の NTT とどう違いますか？

Schönhage-Strassen は p = 2^F · B + 1 の代わりに剰余環 Z/(B^F + 1) 上で NTT を実行する。F が偶数なら 2 が単位根として使えるため、twiddle 乗算がビットシフトだけで済む。sangi の多倍長 Int 乗算は 1,250 ワード以上 (MSVC) または 3,000 ワード以上 (gcc/clang) でまず Prime NTT (3 素数 NTT + CRT) に切り替わり、さらに大規模ケースでは Fermat NTT (Schönhage-Strassen) にフォールバックする。

5-smooth NTT は何が便利ですか？

従来の NTT は N が 2 の冪のときしか高速に動かないため、入力長を 2 のべきにパディングする必要があった。5-smooth NTT は N = 2^a · 3^b · 5^c (5-smooth) でも動作するため、パディングが少なくて済み実効スループットが上がる。sangi の Ntt クラスは 5-smooth サイズを直接処理し、それ以外は Bluestein で 5-smooth に帰着する。

Montgomery 乗算とは何ですか？

Montgomery (1985) が考案した剰余乗算の高速化手法。除算なしで a · b mod p を 2 回の整数乗算と 1 回のシフトに置き換える。sangi の Ntt は AVX2 Montgomery NTT を採用し、各バタフライで剰余乗算がボトルネックにならないように設計されている。

NTT と多倍長整数乗算

概要

数論変換 (Number Theoretic Transform, NTT) は離散フーリエ変換のバタフライを有限体 (素数 $p$ の剰余環や Fermat 数の剰余環) 上で実行する手法である。浮動小数点 FFT と異なり丸め誤差が一切生じないため、多倍長整数乗算・暗号 (NTRU, Kyber 等の格子暗号)・誤り訂正符号など、正確性が要求される領域で広く用いられる。

本記事は sangi での NTT 使用箇所 — 同梱モジュールである Ntt クラスと、 Int 乗算の 1,250 ワード以上 (MSVC) / 3,000 ワード以上 (gcc/clang) で発動する Prime NTT (3 素数 + CRT) 経路、さらに大規模域での Fermat NTT (Schönhage-Strassen) フォールバック — を統一的に解説する。

NTT と FFT の関係

FFT のバタフライ式 $X[k] = E[k] + \omega_N^k O[k]$ で用いる単位根 $\omega_N$ は通常 $e^{-2\pi i / N} \in \mathbb{C}$ である。この $\omega_N$ を有限体 $\mathbb{F}_p$ の $N$ 次原始単位根に置き換えても、同じバタフライ構造で離散フーリエ変換が成立する。

$$\omega_N \in \mathbb{F}_p, \quad \omega_N^N = 1, \quad \omega_N^k \neq 1 \;(0 < k < N)$$

すべての演算が整数の剰余で行われるため、出力も整数で正確 (誤差ゼロ) である。その代償として、$\mathbb{F}_p$ 上に $N$ 次原始単位根が存在するには $N \mid (p - 1)$ が必要となる。

関連記事: 数論変換 (NTT) — NTT の数学的背景・原始根・NTT-friendly 素数・格子暗号への応用を体系的に解説

NTT-friendly 素数

NTT で扱える最大変換長 $N$ は $p - 1$ の 2 の冪因子で決まる。 $p - 1 = c \cdot 2^k$ ($c$ は奇数あるいは小さな合成数) の素数を NTT-friendly 素数 (proth-like 素数) と呼ぶ。

sangi の Ntt は 64-bit 整数空間に収まる以下の 3 つの素数を提供する:

関数	素数 $p$	原始根 $g$	最大 NTT 長
`prime1()`	$30 \times 2^{47} + 1$	19	$2^{47}$
`prime2()`	$345 \times 2^{47} + 1$	13	$2^{47}$
`prime3()`	$420 \times 2^{47} + 1$	17	$2^{47}$

いずれも $p \approx 2^{52}$ で、64-bit 整数の乗算結果が 128-bit に収まる。 $30 = 2 \cdot 3 \cdot 5$、$345 = 3 \cdot 5 \cdot 23$、$420 = 2^2 \cdot 3 \cdot 5 \cdot 7$ という cofactor 構造により、 $p - 1$ が 5-smooth な部分を持ち、5-smooth NTT がそのまま使える。

係数の桁あふれが懸念される場合は 3 素数同時に NTT を実行し、中国剰余定理 (CRT) で結合して有効ビット幅を $\approx 3 \cdot 52 = 156$ bit に拡張できる。

Schönhage-Strassen と Fermat NTT

Schönhage と Strassen (1971) は、剰余環 $\mathbb{Z}/(B^F + 1)$ 上で NTT を行う手法を考案した。ここで $B = 2^{64}$ ($B$ は基数)、$F$ は分割パラメータ。 $B^F + 1$ は Fermat 型の合成数で、$2$ がこの環で $2F$ 次原始単位根 (に近い性質) を持つ。

$$\omega = 2 \in \mathbb{Z}/(B^F + 1), \qquad \omega^{2F} \equiv 1$$

つまり単位根がビットシフトであり、twiddle 乗算が一切不要となる。この性質により Schönhage-Strassen NTT は通常の有限体 NTT より定数倍が小さく、桁数が極端に大きい領域 (数千万桁以上) で漸近的に最速となる。

sangi Int への組み込み

sangi の Int 乗算は Windows MSVC ビルドで 1,250 ワード以上 (約 24,000 桁)、 Linux gcc/clang ビルドで 3,000 ワード以上のときにまず Prime NTT (3 素数 + CRT) 経路に分岐し、さらに大規模域では Fermat NTT (Schönhage-Strassen) にフォールバックする。本節は後者の Fermat NTT を解説する。

整数を $M = 2^l$ 個のピースに分割し、各ピースを $K$ ワード長の整数とみなす。
各ピースを $\mathbb{Z}/(B^F + 1)$ の要素に詰め、$\omega = B^{2F/M}$ を NTT 単位根として使う。
twiddle 乗算はビットシフトのみで実行できる。
点ごとの積は再帰的に通常の (Karatsuba / Toom / 小サイズ NTT) 乗算で計算する。

$M$ と $F$ の選択は piecewise コストモデルで最適化される。詳細は Int 乗算アルゴリズム — NTT を参照。

多項式乗算と整数乗算の双対性

多項式 $a(x) = \sum a_i x^i$ と $b(x) = \sum b_j x^j$ の積の係数は $c_k = \sum_{i+j=k} a_i b_j$ の畳み込みで与えられる。基数 $B$ で表した整数 $a = \sum a_i B^i$, $b = \sum b_j B^j$ の積も同じ畳み込み + キャリー処理で計算できる。

すなわち多倍長整数乗算は「多項式乗算 + キャリー伝播」に分解できる。多項式の係数が大きすぎなければ NTT (有限体 FFT) で正確に畳み込めるため、整数乗算と多項式乗算は計算機代数の同一の基盤を共有する。

多項式乗算 (sangi): FFT::convolve, Ntt::polyMul
整数乗算 (sangi): Int::operator* の Prime NTT 経路 (1,250 ワード以上 MSVC / 3,000 ワード以上 gcc-clang)、大規模域で Fermat NTT
多項式 mod p 乗算: Ntt::polyMul (内部 Montgomery)

関連記事: 高速乗算アルゴリズム / Int 乗算アルゴリズム

5-smooth NTT

従来の NTT は $N \mid (p - 1)$ かつ $N = 2^k$ のときのみ高速だった。 $p - 1$ が小さい奇素因数 (3, 5) を含む NTT-friendly 素数を選べば、$N = 2^a \cdot 3^b \cdot 5^c$ (5-smooth) でも radix-{2,3,5} 混合基数で実行できる。

sangi の Ntt::forward / Ntt::inverse は 5-smooth サイズを直接処理する。 $N$ が 5-smooth でない場合は Bluestein (chirp z 変換) で 5-smooth な畳み込みに帰着する。この設計により、$N$ をぴったりパディングなしで使える機会が増え、平均的なスループットが向上する。

5-smooth でないサイズは Ntt::nextSmoothSize(n) で次の 5-smooth サイズを取得できる。 Ntt::isSmooth(n) は判定のみ行う。

Montgomery 剰余乗算

NTT のバタフライは毎段で $\bmod p$ の乗算を行う。素朴な実装では 64×64 → 128 bit 乗算と 128-bit ÷ 64-bit 除算が必要で、後者がボトルネックとなる。

Montgomery (1985) の手法は乗算を Montgomery 形式 $\tilde{a} = a \cdot R \bmod p$ ($R = 2^{64}$) で保持し、積を計算するときに次の式で還元 (reduction) する:

$$\mathrm{Reduce}(t) = \frac{t + ((t \cdot p') \bmod R) \cdot p}{R} \bmod p, \qquad p' = -p^{-1} \bmod R$$

除算がビットシフトに、剰余が低位ビットの取り出しになり、整数乗算 2 回 + シフトのみで完了する。 AVX2 では 64-bit 整数の SIMD 乗算で 4 並列、結果の高 64 bit と低 64 bit を分離して還元処理を流すことで NTT のバタフライ全体を 5 倍前後高速化できる。

sangi の Ntt は AVX2 Montgomery NTT を採用しており、内部で Montgomery 領域への / からの変換を自動的に行う。ユーザは通常の整数で polyMul を呼べばよい。

sangi Ntt クラス

主要 API を以下に要約する (詳細は FFT API — Ntt を参照)。

関数	用途
`Ntt::forward(data, N, prime)`	順 NTT (in-place)
`Ntt::inverse(data, N, prime)`	逆 NTT ($1/N$ 正規化込み)
`Ntt::pointwiseMul(r, a, b, N, prime)`	NTT 領域の要素ごと乗算
`Ntt::polyMul(r, a, an, b, bn, prime)`	多項式 mod $p$ 乗算 (高水準 API)
`Ntt::nextSmoothSize(n)`	5-smooth へのパディングサイズ
`Ntt::isSmooth(n)`	5-smooth 判定
`Ntt::isValidSize(N, prime)`	$N \mid (p - 1)$ の確認

使い分けのガイド

多項式 mod $p$ の乗算 → Ntt::polyMul (内部で適切なパディングと Montgomery 還元を実行)
低水準で順 → 要素積 → 逆 → forward + pointwiseMul + inverse
大きな整数の乗算 → Int の演算子を使う (1,250 ワード以上で自動的に Prime NTT、大規模域で Schönhage-Strassen)

設計判断

3 素数 NTT の用意

係数桁数が大きい畳み込みでは単一素数では桁あふれする。 3 つの NTT-friendly 素数を CRT で結合することで有効ビット幅を $\approx 156$ bit まで拡張できる。 sangi の prime1/2/3 はこの用途を想定して同じ $2^{47}$ までの NTT 長を持つよう設計されている。

FFT クラスの `ntt` / `intt` は非推奨

過去の互換性のため FFT<ModularInt<P>> 経路に ntt, intt, convolve_ntt が残っているが、現在は非推奨である。新規コードは Ntt クラスを使う。

整数乗算で FFT ではなく NTT を使う理由

浮動小数点 FFT を多倍長整数乗算に使うと、係数桁数 $\log_2 |a_i|$ と FFT 長 $N$ の積が double の仮数ビット (53 bit) を超えると丸め誤差が結果を破壊する。 NTT は剰余環上で正確に計算するため、有効ビット幅の上限がアルゴリズム的に保証され、結果の検証コストが不要となる。

参考文献

Pollard, J. M. (1971). "The Fast Fourier Transform in a Finite Field". Mathematics of Computation, 25, 365–374.
Schönhage, A. and Strassen, V. (1971). "Schnelle Multiplikation großer Zahlen". Computing, 7, 281–292.
Montgomery, P. L. (1985). "Modular Multiplication Without Trial Division". Mathematics of Computation, 44, 519–521.
Crandall, R. and Fagin, B. (1994). "Discrete weighted transforms and large-integer arithmetic". Mathematics of Computation, 62, 305–324.
Harvey, D. (2014). "Faster arithmetic for number-theoretic transforms". Journal of Symbolic Computation, 60, 113–119.