convolution_mod_constants

クラス · internal/internal_fft.hpp

struct convolution_mod_constants;

概要

任意 mod / 任意係数の畳み込みで使う 3 つの NTT-friendly 素数と Garner 法用の定数。 $\mathrm{MOD1} < \mathrm{MOD2} < \mathrm{MOD3}$ で、いずれも $2^{24}$ まで NTT 可能（最小は MOD1 の $2^{24}$）。

関連項目

• convolution_fft_square — 自乗畳み込み (a と a の畳み込み)。順変換が 1 回で済むため通常の 3 NTT に対し 2 NTT で計算できる。
• middle_product_fft — middle product (転置乗算): a（長さ $n$）と b（長さ $m \le n$）に対し $c_i = \sum_{j=0}^{m-1} a_{i+j} b_j$（$i = 0, \ldots, n-m$）を返す（長さ $n-m+1$）。 これは a と $\mathrm{rev}(b)$ のフル積 $a \cdot \mathrm{rev}(b)$ の添字 $m-1, \ldots, n-1$ にあたる。 サイズ $\mathrm{bit\_ceil}(n)$ の巡回畳み込み 1 回で求まる。$z \ge n$ より該当範囲には巻き込みが起きない。