Additive Fast Fourier Transformation

Fast Fourier Transform can be used to evaluate a degree $n-1$ polynomial at $n$ distinct points in time complexity $O(n log n)$. But it’s only possible when the $n$ points are $n$th roots of unity (and so form a cyclic multiplicative group of order $n$ ) where $n$ is a power of 2 or a product of small primes. They are based on the factorization of the polynomial $x^n-1$, corresponding to the subgroup structure of the multiplicative group of order $n$.

Hence, multiplicative FFTs may have little advantage over straightforward evaluation of the $n$ polynomial when over $\mathbb{F}_{2^k}$, because $2^k-1$ is not product of small primes.

Additive fast Fourier transforms over finite field evaluate a polynomial at each roots of polynomial $x^n-x$ (each of the powers of a primitive $(n-1)$th root of unity and the zero element)

Taylor Expansion

First, we want to know how to compute a generalized Taylor expansion of polynomial.

Let $\mathbb{F}$ be any field of characteristic two, $t>1$ any integer, and $f(x) \in \mathbb{F}[x]$ of degree $<n$. We want to find polynomials $h_0(x), h_1(x), \ldots, h_{m-1}(x) \in \mathbb{F}[x]$ such that

$$\begin{aligned} f(x)=h_0(x)+h_1(x) \cdot\left(x^t-x\right)+ & \cdots \\ & +h_{m-1}(x) \cdot\left(x^t-x\right)^{m-1} \end{aligned}$$

where $m = \left \lceil n/t \right \rceil$ and $\deg h_i < t$

First we find $k$ be such that

$$2^k < \frac{n}{t} \leq 2^{k+1}$$

Write $f(x)$ as $f(x)=f_0(x)+x^{t 2^k}\left(f_1(x)+x^{(t-1) 2^k} f_2(x)\right)$ where

$$\begin{aligned} & \operatorname{deg} f_0<t 2^k, \\ & \operatorname{deg} f_1<\min \left(n-t 2^k,(t-1) 2^k\right) \leq(t-1) 2^k, \\ & \operatorname{deg} f_2<2^k \end{aligned}$$

then we have

$$\begin{aligned} f(x)=f_0(x)+ & x^{2^k}\left(f_1(x)+f_2(x)\right) \\ & +\left(x^t-x\right)^{2^k}\left(f_1(x)+f_2(x)+x^{(t-1) 2^k} f_2(x)\right) . \end{aligned}$$

Set $h(x)=f_1(x)+f_2(x)$, and

$$g_0(x)=f_0(x)+x^{2^k} h(x), \quad g_1(x)=h(x)+x^{(t-1) 2^k} f_2(x)$$

Then

$$f(x)=g_0(x)+g_1(x)\left(x^t-x\right)^{2^k}$$

Since $\operatorname{deg} f_1<(t-1) 2^k$ and $\operatorname{deg} f_2<2^k$, we have $\operatorname{deg} h<$ $(t-1) 2^k$, so

$$\operatorname{deg} g_0<t 2^k, \quad \operatorname{deg} g_1<n-t 2^k$$

Therefore

$$\mathrm{T}(f, n, t)=\left(\mathrm{T}\left(g_0, t 2^k, t\right), \mathrm{T}\left(g_1, n-t 2^k, t\right)\right)$$

FFT over $\mathbb{F}_{2^m}$: arbitrary $m$

Let $\mathbb{F}$ be any field of characteristic two. Assume that $\beta_1, \ldots, \beta_m \in \mathbb{F}$ are linearly independent over $\mathbb{F}_2$. Let $B$ be the subspace spanned by $\beta_i$ ‘s over $\mathbb{F}_2$, namely

$$\begin{aligned} B & =\left\langle\beta_1, \ldots, \beta_m\right\rangle \\ & =\left\{a_1 \beta_1+\cdots+a_m \beta_m: a_1, \ldots, a_m \in \mathbb{F}_2\right\} . \end{aligned}$$

We order the elements of $B$ as follows:

$$B[i] = a_1\beta_1 + a_2\beta_2+\dots + a_m \beta_m$$

where each $a_j = 0 \text{ or } 1$. Then

$$\operatorname{FFT}(f, m, B)=(f(B[0]), f(B[1]), \ldots, f(B[n-1])) .$$

Define

$$\begin{aligned} &\gamma_i=\beta_i \cdot \beta_m^{-1}, \quad 1 \leq i \leq m-1\\ \end{aligned}$$

and

$$\begin{aligned} G & =\left\langle\gamma_1, \ldots, \gamma_{m-1}\right\rangle \\ & =\left\{a_1 \gamma_1+\cdots+a_{m-1} \gamma_{m-1}: a_1, \ldots, a_{m-1} \in \mathbb{F}_2\right\} . \end{aligned}$$

Let $g(x) = f(\beta_m x)$, then evaluating $f(x)$ over $B$ is the same as evaluating $g(x)$ over $B\cdot \beta_m^{-1}=G\cup (G+1)$ where $G+1=\{\alpha+1: \alpha \in G\}$.

$$\begin{aligned} G & =\left\langle\gamma_1, \ldots, \gamma_{m-1}\right\rangle \\ & =\left\{a_1 \gamma_1+\cdots+a_{m-1} \gamma_{m-1}: a_1, \ldots, a_{m-1} \in \mathbb{F}_2\right\}\\ &=\left\{a_1 \beta_1\beta_m^{-1}+\cdots+a_{m-1} \beta_{m-1}\beta_{m-1}^{-1} + a_m\beta_m\beta_m^{-1}: a_1, \ldots, a_{m-1} \in \mathbb{F}_2, a_m=0\right\}\\ \end{aligned}$$

and

$$\begin{aligned} G+1& = \left\{a_1 \beta_1\beta_m^{-1}+\cdots+a_{m-1} \beta_{m-1}\beta_{m-1}^{-1} + a_m\beta_{m}\beta_m^{-1}: a_1, \ldots, a_{m-1} \in \mathbb{F}_2,a_m=1\right\}\\ \end{aligned}$$

Then we can get

$$\begin{aligned} \operatorname{FFT}(f, m, B) & \\ & =(\operatorname{FFT}(g, m-1, G), \operatorname{FFT}(g, m-1, G+1)) \end{aligned}$$

We need to show how to compute $\operatorname{FFT}(g, G)$ and $\operatorname{FFT}(g, G+1)$. Define

$$\delta_i=\gamma_i^2-\gamma_i, \quad 1 \leq i \leq m-1$$

and

$$\begin{aligned} D & =\left\langle\delta_1, \ldots, \delta_{m-1}\right\rangle \\ & =\left\{a_1 \delta_1+\cdots+a_{m-1} \delta_{m-1}: a_1, \ldots, a_{m-1} \in \mathbb{F}_2\right\} . \end{aligned}$$

Since $\gamma_1, \ldots, \gamma_{m-1}$ and 1 are linearly independent over $\mathbb{F}_2$, the new elements $\delta_1, \ldots, \delta_{m-1}$ are linearly independent over $\mathbb{F}_2$, so $D$ is a subspace of $\mathbb{F}$ of size $k=2^{m-1}=n / 2$. For each $\alpha=a_1 \gamma_1+\cdots+a_{m-1} \gamma_{m-1} \in G$, let

$$\alpha^*=\alpha^2-\alpha=a_1 \delta_1+\cdots+a_{m-1} \delta_{m-1} \in D$$

Then we have

$$G[i]^*=D[i], \quad 0 \leq i<k$$

where $G[i]$ and $D[i]$ are the $i$ th elements of $G$ and $D$, respectively, which are ordered according to the binary representation of $i$ in a similar fashion as that described above for $B$.

Suppose the Taylor expansion of $g(x)$ at $x^2-x$ is

$$g(x)=\sum_{i=0}^{k-1}\left(g_{i 0}+g_{i 1} x\right) \cdot\left(x^2-x\right)^i$$

where $g_{i j} \in \mathbb{F}$. Let

$$g_0(x)=\sum_{i=0}^{k-1} g_{i 0} \cdot x^i, \quad \text { and } g_1(x)=\sum_{i=0}^{k-1} g_{i 1} \cdot x^i$$

For any $\alpha \in G$ and $b \in \mathbb{F}_2$, since $(\alpha+b)^2-(\alpha+b)=\alpha^*$, we have,

$$g(\alpha+b)=\left(g_0\left(\alpha^*\right)+\alpha \cdot g_1\left(\alpha^*\right)\right)+b g_1\left(\alpha^*\right) .$$

Hence the FFT of $g(x)$ can be obtained from those of $g_0(x)$ and $g_1(x)$ as follows. Let the FFT of $g_0(x)$ and $g_1(x)$ over $D$ be

$$\begin{aligned} & \operatorname{FFT}\left(g_0, m-1, D\right)=\left(u_0, u_1, \ldots, u_{k-1}\right), \\ & \operatorname{FFT}\left(g_1, m-1, D\right)=\left(v_0, v_1, \ldots, v_{k-1}\right) \end{aligned}$$

where $u_i=g_0(D[i])$ and $v_i=g_1(D[i]), 0 \leq i<k$. Then the equation (5) implies that

$$\operatorname{FFT}(g, m-1, G)=\left(w_0, w_1, \ldots, w_{k-1}\right)$$

where $w_i=u_i+G[i] \cdot v_i$ for $0 \leq i<k$, and

$$\begin{aligned} & \operatorname{FFT}(g, m-1, G+1) \\ & \quad=\operatorname{FFT}(g, m-1, G)+\operatorname{FFT}\left(g_1, m-1, D\right) . \end{aligned}$$

FFT over $\mathbb{F}_{2^m}$: $m$ a power of two

Todo

Reference

[1] Additive Fast Fourier Transforms Over Finite Fields