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?