Fast Fourier Transform In Finite Field

We discuss the fast Fourier transform in a finite field $\mathbb{F}$ with size $p$.

For $w \in \mathbb{F}$, and $n \in \mathbb{F}_+$, define

$$M_{w, n} \doteq \begin{bmatrix} 1 &w &w^2 &... &w^{n - 1} \\ 1 &w^2 &w^4 &... &w^{2(n - 1)} \\ ... \\ 1 &w^{n} &w^{2n} &... &w^{n(n - 1)} \end{bmatrix}.$$

If the following two conditions hold:

1. $n$ is some power of $2$ and;
2. $w^n = 1$ in the finite field.

Then $\forall \vec x \doteq (x_1, x_2, ..., x_n) \in \mathbb{F}^n$, we can compute

$$M_{w, n} \vec x = \begin{bmatrix} 1 &w &w^2 &... &w^{n - 1} \\ 1 &w^2 &w^4 &... &w^{2(n - 1)} \\ ... \\ 1 &w^{n} &w^{2n} &... &w^{n(n - 1)} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ ... \\ x_n \end{bmatrix}$$

in $O(n \log n)$ time.

Proof. If $n = 2$, then the claim holds trivially.

Otherwise, let $d = n / 2 = 2^{k - 1}$ and $v = w^2$. The odd columns of the first $d$ rows of the matrix $M_{w, n}$ constitutes

By assumption, for even numbers $i = 2, 4, ..., (n - 2)$, we have $i \cdot d = 1$ in the finite field. Hence, the odd columns of the last $d$ rows of $M_{w, n}$ is

Let $\vec x_o, \vec x_e \in \mathbb{F}^d$ be the vectors obtained by the odd and even dimensions of $\vec x$ respectively. By our construction,

1. $d$ is some power of $2$ and;
2. $v^d = w^n = 1$.

Hence, by induction hypothesis we can compute $M_{v, d} \vec x_o$ in $O(d \log d) = O( n \log n)$ time.

Next, consider the even columns of the first $d$ rows of the matrix $M_{w, n}$ constitutes

Similarly, the even columns of the last $d$ rows of the matrix $M_{w, n}$ constitutes

The equality comes from that $w^d = w^{n / 2} = -1$. By induction hypothesis, we can compute $M_{v, d} \vec x_e$ in $O(n \log n)$ time.

Finally, the first $d$ dimensions of $M_{w, n} \vec x$ equals

which can be computed in $O(n \log n) + O(n \log n) + O(n) = O(n \log n)$ time.

The last $d$ dimensions of $M_{w, n} \vec x$ equals

which can also be computed in $O(n \log n) + O(n \log n) + O(n) = O(n \log n)$ time.

$\square$