加法的FFT (Additive Fast Fourier Transform) について

理情 Advent Calendar 2025の18日目の記事です。

加法的FFT (Additive Fast Fourier Transform) とは

$f, g \in \mathbb{F}_2[x]$の積を計算する事を考える。有限体上の多項式の乗算を高速化する方法として、NTT (Number Theoretic Transform)を用いた畳み込みを用いた手法が一般的である。NTTでは与えられた$f, g$を$\mathbb{F}_{2^d}$の乗法部分群の各元で評価し、その結果をかけ合わせたうえで逆変換を行うことで$f \cdot g$を求める。しかしながら$\mathbb{F}_2[x]$の場合は、乗法部分群の位数$\left|\mathbb{F}_{2^d}^{\times}\right| = 2^d - 1$が一般に小さな素因数を多く持つとは限らないため、効率的にNTTを行うことができない。

そこで、$\mathbb{F}_{2^d}$の乗法群の代わりに、$\mathbb{F}_{2^d}$の加法的部分空間を評価点として用いるのが加法的FFT (AFFT, Additive Fast Fourier Transform)である¹。この記事では[1]を参考に、AFFTを計算するアルゴリズムの$1$つを説明する。

問題設定

$\mathbb{F}$を位数$2^d$、標数$2$の有限体とし、$d$は$2$冪であるとする。また$m \leq d$とし、簡単のため$m$も$2$冪であるとする²。$\mathbb{F}$を$\mathbb{F}_2$-線型空間とみた基底として$\beta_1, \ldots, \beta_d \in \mathbb{F}$を適当に固定し、$0 \leq i < 2^m$に対して$i$の$2$進展開を用いて$\varpi_i \in \mathbb{F}$を次のように定める。
$$
\varpi_i = \sum_{j=1}^{m} a_j \beta_j \quad \left( i = \sum_{j=1}^{m} a_j 2^{j-1},\space a_j \in {0, 1} \right)
$$

ここで、次数が$n = 2^m$未満の多項式$f \in \mathbb{F}[x]$と$a \in \mathbb{F}$が与えられる。$f$を$\beta_1, \ldots, \beta_m$が張る部分空間$B = \langle \beta_1, \ldots, \beta_m \rangle \subset \mathbb{F}$に対して$a + B$の各元で評価した値$f(a + b)$ ($b \in B$)を計算する。すなわち、以下のように$0 \leq i < 2^m$に対して$f(a + \varpi_i)$を求める問題を考える。
$$
(f(a + \varpi_0), f(a + \varpi_1), \ldots, f(a + \varpi_{2^m - 1}))
$$

もし$f, g \in \mathbb{F}_2[x]$の積を計算したい場合は、$\mathbb{F} \cong \mathbb{F}_2[u] / (p(u))$の同型の元で$F(x) = \sum_{i=0}^{2n / d} x^i \sum_{j=0}^{d/2-1} f_{di+j} u^j \in \mathbb{F}_{2^d}[x]$とみなす。同様に$G(x)$も定める。$\deg(F) + \deg(G) < 2^m$を満たすように$m$を選び、$a=0$のAFFTを用いて$B$上で$F, G$を評価、その結果をかけ合わせた後、逆AFFTを用いて$F \cdot G$を求めることで$f \cdot g$を計算できることに注意する。

また$\mathbb{F}$の元の加算、乗算は$\Theta(1)$時間であるとする³。

Taylor展開

準備として、$t \in \mathbb{Z}_{\geq 2}, \space f \in \mathbb{F}[x] \space (\deg(f) < n)$に対して次のように$f$のTaylor展開を定義する⁴。
$$
f(x) = \sum_{i=0}^{K-1} h_i (x) \cdot (x^t + x)^i
$$
ここで$K = \lceil n / t \rceil$で$h_i \in \mathbb{F}[x]$は$\deg(h_i) < t$を満たす多項式である。このような展開は一意であることに注意する。

$f \in \mathbb{F}[x]$が与えられたときそのTaylor展開を次のように書くことにする。
$$
\mathrm{T}(f, n, t) = (h_0, h_1, \ldots, h_{K-1})
$$

$\mathrm{T}(f, n, t)$は次のように計算できる。$n < t$のときは$f$をそのまま返せば良い。$n \geq t$とする。まず$2^k < n / t \leq 2^{k+1}$を満たす$k \in \mathbb{Z}_{\geq 0}$をとる。$f$を次のように分割する。
$$
f(x) = f_0 (x) + x^{t 2^k} \left(f_1 (x) + x^{(t-1) 2^k} f_2 (x) \right)
$$
ここで$\deg(f_0) < t 2^k, \space \deg(f_1) < \min\left(n - t 2^k, (t-1) 2^k \right), \space \deg(f_2) < 2^k$である。このとき$\mathbb{F}$の標数は$2$であることに注意して、以下が成り立つ。
$$
\begin{aligned}
f(x) &= f_0 (x) + x^{t 2^k} \left(f_1 (x) + x^{(t-1) 2^k} f_2 (x) \right) \\
&= f_0(x) + \left( x^{t 2^k} + x^{2^k} + x^{2^k} \right) \left(f_1 (x) + x^{(t-1) 2^k} f_2 (x) \right) \\
&= f_0(x) + \left( (x^t + x)^{2^k} + x^{2^k} \right) \left(f_1 (x) + x^{(t-1) 2^k} f_2 (x) \right) \\
&= f_0 (x) + x^{2^k} f_1(x) + \left(x^{t 2^k} - (x^t + x)^{2^k} \right) f_2 (x) + (x^t + x)^{2^k} \left(f_1 (x) + x^{(t-1) 2^k} f_2 (x) + f_2 (x)\right) \\
&= f_0 (x) + x^{2^k} (f_1 (x) + f_2 (x)) + (x^t + x)^{2^k} \left(f_1 (x) + x^{(t-1) 2^k} f_2 (x) + f_2 (x)\right)
\end{aligned}
$$
$\deg\left(f_0 + x^{2^k} (f_1 + f_2)\right) < t 2^k$と$\deg\left(f_1 + x^{(t-1) 2^k} f_2 + f_2\right) < n - t 2^k$であることに注意すると、再帰的にTaylor展開を計算できる。つまり以下のようにすれば良い。
$$
\mathrm{T}(f, n, t) = \left(T(f_0 + x^{2^k} (f_1 + f_2), t 2^k, t), \space T(f_1 + x^{(t-1) 2^k} f_2 + f_2, n - t 2^k, t) \right)
$$
再帰の深さは$\Theta(\log (n / t))$であり、各レベルで行う計算量は$\Theta(n)$であるため、全体の時間計算量は$\Theta(n \log (n / t))$である。

Cantor基底

この問題設定において、$\mathbb{F}$の基底$\beta_1, \ldots, \beta_d$の選択には自由度がある。ここではCantor基底と呼ばれる特別な基底を用いる。Cantor基底は次のように構成される。まず$\beta_d \in \mathbb{F}$を$\mathrm{Tr}_{\mathbb{F} / \mathbb{F}_2} (\beta_d) = 1$を満たすように選ぶ⁵。$\beta_1, \ldots, \beta_{d-1}$は次のように再帰的に定義される。
$$
\beta_i = \beta_{i+1}^2 + \beta_{i+1} \quad (1 \leq i < d)
$$

また$0 \leq k \leq d$に対して部分空間$W_k \subset \mathbb{F}$を次のように定める。
$$
W_k = \langle \beta_1, \beta_2, \ldots, \beta_k \rangle
$$
ここで$0 = W_0 \subset W_1 \subset \cdots \subset W_d = \mathbb{F}$となることに注意する。また$s_k \in \mathbb{F}[x]$を次のように定める。
$$
s_k (x) = \prod_{b \in W_k} (x - b)
$$

いくつかの補題を示す。

---

補題1

$\phi: \mathbb{F} \to \mathbb{F}, \space x \mapsto x^2 + x$としたとき$\phi$は加法的であり、また$1 \leq i < d$に対して$\beta_i = \phi(\beta_{i+1})$が成り立つ。

証明

$\mathbb{F}$は標数$2$より$\phi$は加法的である。構成より$\beta_i = \phi(\beta_{i+1})$は明らか。

---

補題２

以下が成り立つ。
$$
\phi^i (x) = \sum_{j=0}^{i} \binom{i}{j} x^{2^j} \in \mathbb{F}[x]
$$
また$\beta_1 = \phi^{d-1} ( \beta_d ) = 1$である。

証明

帰納法で示す。$i = 0$のとき、$\phi^0 (x) = x = \sum_{j=0}^{0} \binom{0}{j} x^{2^j}$である。

$i > 0$とする。このとき$\phi^i (x) = \sum_{j=0}^{i} \binom{i}{j} x^{2^j}$は以下のように示せる。
$$
\begin{aligned}
\phi^i (x) &= \phi^{i-1} \left( \phi (x) \right) \\
&= \sum_{j=0}^{i-1} \binom{i-1}{j} \left( x^2 + x \right)^{2^j} \\
&= \sum_{j=0}^{i-1} \binom{i-1}{j} \left( x^{2^{j+1}} + x^{2^j} \right) \\
&= \binom{i-1}{0} x^{2^0} + \sum_{j=1}^{i-1} \left( \binom{i-1}{j-1} + \binom{i-1}{j} \right) x^{2^j} + \binom{i-1}{i-1} x^{2^i} \\
&= \sum_{j=0}^{i} \binom{i}{j} x^{2^j}
\end{aligned}
$$

また、$0 \leq j < d-1$の$2$進展開を$j_1, \ldots, j_k$とすると、Lucasの定理と$d$が$2$冪であることと合わせて$\binom{d-1}{j} \equiv \binom{1}{j_1} \cdots \binom{1}{j_k} \equiv 1$となるため、以下が成り立つ。
$$
\begin{aligned}
\beta_1 &= \phi^{d-1} ( \beta_d ) \\
&= \sum_{j=0}^{d-1} \binom{d-1}{j} \beta_d^{2^j} \\
&= \sum_{j=0}^{d-1} \beta_d^{2^j} \\
&= \mathrm{Tr}_{\mathbb{F} / \mathbb{F}_2} (\beta_d) \\
&= 1
\end{aligned}
$$

---

補題3

$\beta_1, \ldots, \beta_d$は$\mathbb{F}$の基底である。

証明

$\beta_1, \ldots, \beta_d$が線型独立であることを示せば良い。$\beta_1, \ldots, \beta_k$が線形独立であることを$k$について帰納法で示す。

$k = 1$のとき、$\beta_1 = 1 \neq 0$であるため線型独立である。$k > 1$とする。もし仮に$\beta_k = \sum_{i=1}^{k-1} a_i \beta_i$ ($a_i \in \mathbb{F}_2$)と表せるとする。両辺$\phi$を取ると$\beta_{k-1} = \sum_{i=1}^{k-2} a_{i+1} \beta_{i}$となり、$\beta_1, \ldots, \beta_{k-1}$が線型従属であることになる。これは帰納法の仮定に反するため、$\beta_1, \ldots, \beta_k$は線型独立である。

---

補題4

以下が成り立つ。
$$
s_i(x) = \phi^i(x) \in \mathbb{F}[x]
$$
$\mathbb{F}$は標数$2$より$\phi$は加法的であり、$s_i(x)$も加法的となる。

証明

帰納法で示す。$i = 0$のとき、$s_0(x) = x - 0 = x = \phi^0(x)$である。

$i > 0$とする。このとき以下のように示せる。
$$
\begin{aligned}
s_i (x) &= \prod_{b \in W_i} (x - b) \\
&= \prod_{b \in W_{i-1}} (x - b) \prod_{b \in W_{i-1}} (x - (b + \beta_i)) \\
&= s_{i-1}(x) \cdot s_{i-1}(x - \beta_i) \\
&= \phi^{i-1}(x) \cdot \phi^{i-1}(x - \beta_i) \\
&= \phi^{i-1}(x)\left( \phi^{i-1}(x) - \phi^{i-1}(\beta_i) \right) \\
&= \phi^{i-1}(x)^2 - \phi^{i-1}(x) \cdot \beta_1 \\
&= \phi^i(x)
\end{aligned}
$$

---

補題5

$k$が$2$冪のとき、以下が成り立つ。
$$
s_k(x) = \phi^k(x) = x^{2^k} + x \in \mathbb{F}[x]
$$
また$i 2^k < 2^m$が満たされるなら$\varpi_{i 2^k}^{2^k} + \varpi_{i 2^k} = \varpi_i$が成り立つ。

証明

Lucasの定理より、$1 \leq j < k$に対して$\binom{k}{j} \equiv 0$となるため、補題2を用いると以下のように示せる。
$$
s_k(x) = \phi^k(x) = \sum_{j=0}^{k} \binom{k}{j} x^{2^j} = \binom{k}{k} x^{2^k} + \binom{k}{0} x^{2^0} = x^{2^k} + x
$$

ここで$i$の$2$進展開を$i = \sum_{j=1}^{m} a_j 2^{j-1}$として上の式に$x \leftarrow \varpi_{i 2^k}$を代入する。
$$
\begin{aligned}
\varpi_{i 2^k}^{2^k} + \varpi_{i 2^k}
&= s_k (\varpi_{i 2^k}) \\
&= s_k \left( \sum_{j=1}^{m} a_j \beta_{j+k} \right) \\
&= \sum_{j=1}^{m} a_j s_k (\beta_{j+k}) \\
&= \sum_{j=1}^{m} a_j \beta_j \\
&= \varpi_i
\end{aligned}
$$

---

加法的FFTのアルゴリズム

以上で加法的FFTの準備が整った。

$m = 1$のときは$W_1 = {0, 1}$より$f(0), f(1)$を直接計算すれば良い。以下では$m \geq 2$とする。

このアルゴリズムはサイズ$n = 2^m$の問題を$2\sqrt n$個のサイズ$\sqrt n = 2^{m/2}$の問題へ分割統治することで計算を行う。具体的には評価点$a + \varpi_0, \ldots, a + \varpi_{n-1}$を$2^{m / 2}$個ずつの合計$2^{m / 2}$個のブロックに分割する。$i$番目 ($0 \leq i < 2^{m/2}$) のブロックは次のようになる。
$$
\left( a + \varpi_{i 2^{m/2}}, a + \varpi_{i 2^{m/2} + 1}, \ldots, a + \varpi_{(i+1) 2^{m/2} - 1} \right)
$$

それぞれの$i$について、$i$番目のブロックで$f$を高速に評価することができればよい。ここで剰余の定理より、$f$を次の多項式におきかえてもブロック$i$での評価値は変わらない。
$$
f(x) \bmod \prod_{j=0}^{2^{m/2} - 1} (x - (a + \varpi_{i 2^{m/2} + j}))
$$
このとき$m/2$が$2$冪であることに注意して補題5より以下が成り立つ。
$$
\begin{aligned}
\prod_{j=0}^{2^{m/2} - 1} (x - (a + \varpi_{i 2^{m/2} + j}))
&= \prod_{j=0}^{2^{m/2} - 1} (x - a - \varpi_{i 2^{m/2}} - \varpi_j) \\
&= \prod_{b \in W_{m/2}} (x - a - \varpi_{i 2^{m/2}} - b) \\
&= s_{m/2} (x - (a + \varpi_{i 2^{m/2}})) \\
&= (x - (a + \varpi_{i 2^{m/2}}))^{2^{m/2}} + (x - (a + \varpi_{i 2^{m/2}})) \\
&= x^{2^{m/2}} + x - \left(a^{2^{m/2}} + a\right) - \left( \varpi_{i 2^{m/2}}^{2^{m/2}} + \varpi_{i 2^{m/2}} \right)\\
&= x^{2^{m/2}} + x - c - \varpi_i
\end{aligned}
$$
ただし$c = a^{2^{m/2}} + a$とした。

ところで、$f$のTaylor展開を$f(x) = \sum_{j=0}^{2^{m/2} - 1} h_j (x) \cdot (x^{2^{m/2}} + x)^j$とする。また$h_j(x) = \sum_{k=0}^{2^{m/2} - 1} h_{j,k} x^k$と展開する。このとき多項式$g_k$を次のように定める。
$$
g_k (x) = \sum_{j=0}^{2^{m/2} - 1} h_{j,k} x^j
$$
このときブロック$i$で評価すべき多項式は次のように書き換えられる。
$$
\begin{aligned}
& f(x) \pmod {x^{2^{m/2}} + x - c - \varpi_i} \\
\equiv& \sum_{j=0}^{2^{m/2} - 1} h_j (x) \cdot (x^{2^{m/2}} + x)^j \\
\equiv& \sum_{j=0}^{2^{m/2} - 1} h_j (x) \cdot (c + \varpi_i)^j \\
\equiv& \sum_{k=0}^{2^{m/2} - 1} g_k (c + \varpi_i) x^k
\end{aligned}
$$
よく見ると、この多項式の係数は$g_k$を$\varpi_i + c$で評価した値である。つまりそれぞれのブロックで計算するべき多項式の係数は再帰的に$g_0, \ldots, g_{2^{m/2} - 1}$をそれぞれ$W_{m/2} + c$で評価することで求められる。

この評価によりブロック$i$で計算するべき多項式が$f_i$として得られたとする。$\deg(f_i) < 2^{m/2}$であることに注意すると、評価する点は$a + \varpi_{i 2^{m/2} + j} = \left(a + \varpi_{i 2^{m/2}}\right) + \varpi_j$であるため、再び再帰的に$f_i$を$a + \varpi_{i 2^{m/2}} + W_{m/2}$で評価すれば良い。以上より、加法的FFTを再帰的に計算することができた。

ここまでのアルゴリズムをまとめると以下のようになる。

$$
\begin{array}{l}
\mathbf{Algorithm:}\ \text{AFFT}(f, a, m) \\
\hline
\mathbf{if}\ m = 1\ \mathbf{then} \\
\quad \mathbf{return}\ (f(a), f(a + 1)) \\
\mathbf{else} \\
\quad (h_0, h_1, \ldots, h_{2^{m/2} - 1}) \leftarrow \mathrm{T}(f, 2^m, 2^{m/2}) \\
\quad \text{for } k = 0 \text{ to } 2^{m/2} - 1 \text{ do} \\
\quad \quad g_k (x) \leftarrow \sum_{j=0}^{2^{m/2} - 1} h_{j} [k] x^j \\
\quad \text{end} \\
\quad c \leftarrow a^{2^{m/2}} + a \\
\quad \text{for } k = 0 \text{ to } 2^{m/2} - 1 \text{ do} \\
\quad \quad \text{let } f^\ast_k = \mathbf{AFFT}(g_k, c, m/2) \\
\quad \text{end} \\
\quad \text{for } i = 0 \text{ to } 2^{m/2} - 1 \text{ do} \\
\quad \quad f_i (x) \leftarrow \sum_{k=0}^{2^{m/2} - 1} f^*_k [i] x^k \\
\quad \quad \text{let } \text{block}_i = \mathbf{AFFT}(f_i, a + \varpi_{i 2^{m/2}}, m/2) \\
\quad \text{end} \\
\quad \mathbf{return}\ (\text{block}_0, \text{block}_1, \ldots, \text{block}_{2^{m/2} - 1}) \\
\mathbf{end}
\end{array}
$$

この再帰の深さは$\Theta(\log m) = \Theta(\log \log n)$であり、各レベルで行う時間計算量は$\Theta(n \log n)$であるため、全体の時間計算量は$\Theta(n \log n \log \log n)$となる。またアルゴリズムの各部分の操作は簡単に逆変換が作れるため、逆AFFTも同様の計算量で実装できる。体の位数は$2^d$であるため、$\mathbb{F}$の演算が$\Theta(1)$でできる仮定の元、$N$ bitの$\mathbb{F}_2$上の多項式の乗算は$\Theta(N \log N\log \log N / d)$で計算できることになる。

参考文献

[1]: Shuhong Gao and Todd Mateer, "Additive Fast Fourier Transforms over Finite Fields", IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6265-6272, 2010.

[2]: Wen-Ding Li, Ming-Shing Chen, Po-Chun Kuo, Chen-Mou Cheng, Bo-Yin Yang, "Frobenius Additive Fast Fourier Transform", ISSAC 2018.

1. Additive FFTの日本語の定訳は存在しないようなため、ここでは「加法的FFT」と呼ぶことにする。 ↩

2. ここの$m$が$2$冪であるという仮定はFrobenius加法的FFTを用いれば計算量を変えずに取り除けることが知られている。[2]を参照。 ↩

3. 適当な表現を用いれば、加算はbitwise XOR、乗算はPCLMULQDQ命令などが利用できる。 ↩

4. $x^t - x$を別の多項式置き換えた一般のTaylor展開もある。 ↩

5. ここで$\beta_d \in \mathbb{F}$をランダムに選べば、$\mathrm{Tr}_{\mathbb{F} / \mathbb{F}_2} (\beta_d) = 1$を満たす確率は$1/2$であるため、例えば乱択できる。 ↩