Fast convolution over small finite fields

Question

What are the best known methods for cyclic convolution of length $n$ over a small field, i.e. when $|\mathbb{F}| \ll n$? I'm particularly interested in constant-sized fields, or even $\mathbb{F} = \mathbb{F}_2$. General asymptotic-efficiency statements and references are much appreciated.

Background: Let $\mathbb{F}$ be a field, and $n > 0$. We think of vectors $u \in \mathbb{F}^n$ as having coordinates indexed by $\mathbb{Z}_n$.

The (cyclic) convolution of length $n$ over $\mathbb{F}$ is the transformation taking $u, v \in \mathbb{F}^n$ and outputting $u * v \in \mathbb{F}^n$, defined by $$ (u * v)_i := \sum_{j \in \mathbb{Z}_n} v_j u_{i - j}, $$ with index arithmetic over $\mathbb{Z}_n$.

To perform cyclic convolution over large fields, a popular method is to use the Convolution Theorem to reduce our problem to performing Discrete Fourier Transforms (DFTs), and using an FFT algorithm.

For small finite fields, the DFT is undefined because there's no primitive $n$-th root of unity. One can get around this by embedding$^*$ the problem in a larger finite field, but it's not clear that this is the best way to proceed. Even if we take this route, it'd be nice to know if someone has already worked out the details (for example, choosing which larger field to use and which FFT algorithm to apply).

Added:

$^*$ By 'embedding' our convolution in, I mean one of two things. First option: one could pass to an extension field in which the desired primitive roots of unity are adjoined, and do the convolution there.

Second option: if our starting field is cyclic, one could pass to a cyclic field $\mathbb{F}_{p'}$ of larger characteristic--large enough that if we consider our vectors as lying in $\mathbb{F}_{p'}$, no "wraparound" occurs.
(I'm being informal, but just think about how, to compute a convolution over $\mathbb{F}_2$, we can clearly just do the same convolution over $\mathbb{Z}$, and then take the answers mod 2.)

Also added:

Many algorithms for FFT and related problems work especially well for 'nice' values of $n$ (and I would like to understand the situation with this better).

But if one doesn't attempt to take advantage of special values of $n$, the cyclic convolution problem is basically equivalent (by easy reductions involving linear blow-up in $n$) to ordinary convolution; this in turn is equivalent to multiplication of polynomials with coefficients over $\mathbb{F}_p$.

By this equivalence, one can use results in, e.g., this paper of von zur Gathen and Gerhard (building on work of Cantor), who use an extension-field approach to get a circuit complexity bound of $\tilde{O}_p(n)$. They don't state their bounds in an especially clear way IMO, but the bound is worse than $n \cdot \log^2 n$ even for $\mathbb{F}_2$. Can one do better?

Answer 1

A recent paper by Alexey Pospelov appears to give the state of the art. (It isn't the first to achieve the bounds I'll quote, but it achieves them in a unified way for arbitrary fields, and equally importantly, it states the bounds clearly, see p. 3.)

$\bullet$ We can multiply two degree-$n$ polynomials over an arbitrary field $\mathbb{F}$ using $O(n \log n)$ multiplications in $\mathbb{F}$ and $O(n \log n \log \log n)$ additions in $\mathbb{F}$. This is originally due to Schonhage-Strassen (for char. $\neq 2$) and Schonhage for char. 2. As I mentioned, this implies the same bounds for cyclic convolution. Pospelov also states, "We are currently not aware of any algorithms with an upper bound of [the above] that are not based on consecutive DFT applications..."

$\bullet$ Cantor and Kaltofen generalized these results, showing the bounds hold for arbitrary algebras (not just fields).

$\bullet$ If $\mathbb{F}$ supports Discrete Fourier Transform of appropriate order, that is, if $\mathbb{F}$ has a primitive $N$-th root of unity where $N$ is large enough (I believe $N = O(n)$ suffices) and $N$ is a power of 2 or 3, then we can do polynomial multiplication with $O(n)$ multiplications and $O(n \log n)$ additions. Various other improvements are possible for fields with other special properties.

$\bullet$ It seems to be plausible, but unknown, whether Furer's recent improvement in integer multiplication (reproved in a different way by De et al.) can help lead to faster polynomial multiplication algorithms, over finite fields say. Can anyone comment?

Todd Mateer's thesis also seems like an excellent resource to understand the FFT literature and applications to polynomial multiplication (thanks Jug!); but you have to dig more to find what you're looking for.