<p>A recent <a href="http://eccc.hpi-web.de/report/2010/152/" rel="nofollow">paper</a> 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.)</p>

<p>$\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..."</p>

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

<p>$\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.</p>

<p>$\bullet$ It seems to be plausible, but unknown, whether Furer's recent <a href="http://www.cse.psu.edu/~furer/Papers/mult.pdf" rel="nofollow">improvement</a> in integer multiplication (<a href="http://arxiv.org/abs/0801.1416" rel="nofollow">reproved</a> in a different way by De et al.) can help lead to faster polynomial multiplication algorithms, over finite fields say.  Can anyone comment?</p>

<p>Todd Mateer's <a href="http://cr.yp.to/f2mult/mateer-thesis.pdf" rel="nofollow">thesis</a> 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.</p>

CC BY-SA 3.0
2011-07-29T00:57:26.487Z
I think you are right on Furer and De. De does not use complex version of FFT and seems to be easier technically although both algorithms are similar conceptually.
v s
CC BY-SA 3.0
2011-08-02T13:31:02.863Z
If you are worried about log factors you need to be careful about the machine model.  Furer's recent improvement is specifically for Turing machines. For a unit cost RAM model (even without multiplication but with constant time lookup) you get O(n) time for multiplying two n bit numbers and correspondingly lower time complexities for multiplication over F_2 etc. using bit packing and classic techniques.
Simd
CC BY-SA 3.0
2011-07-28T21:20:51.767Z
2011-07-28T21:20:51.767Z
Andy Drucker
<p>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.</p>

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

<p>The <em>(cyclic) convolution</em> 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$.</p>

<p>To perform cyclic convolution over large fields, a popular method is to use the <a href="http://en.wikipedia.org/wiki/Convolution_theorem">Convolution Theorem</a> to reduce our problem to performing Discrete Fourier Transforms (DFTs), and using an FFT algorithm.</p>

<p>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).</p>

<p><strong>Added:</strong></p>

<p>$^*$ 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.  </p>

<p>Second option: if our starting field is cyclic, one could pass to a cyclic field $\mathbb{F}_{p&#39;}$ of larger characteristic--large enough that if we consider our vectors as lying in $\mathbb{F}_{p&#39;}$, no "wraparound" occurs.<br>
(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.)</p>

<p><strong>Also added:</strong></p>

<p>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).  </p>

<p>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$.  </p>

<p>By this equivalence, one can use results in, e.g., <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.8160">this paper</a> 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?</p>

CC BY-SA 3.0
2011-07-28T10:32:24.863Z
Maybe you find something useful in the [thesis of Todd Mateer](http://cr.yp.to/f2mult/mateer-thesis.pdf).
j.p.
CC BY-SA 3.0
2014-06-08T01:38:49.777Z
I asked [a very similar question](http://mathoverflow.net/questions/40485/ffts-over-finite-fields) on MathOverflow for computing the DFT over arbitrary finite fields; you might find the answers relevant.
Bill Bradley
<ds.algorithms><reference-request>
Fast convolution over small finite fields
Andy Drucker
# Fast convolution over small finite fields

(Asked by: username_0 on 2011-07-27)

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](http://en.wikipedia.org/wiki/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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.8160) 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?

**Tags:** ds.algorithms, reference-request

> **Comments:**
> **username_1**: Maybe you find something useful in the [thesis of Todd Mateer](http://cr.yp.to/f2mult/mateer-thesis.pdf).  
> **username_2**: I asked [a very similar question](http://mathoverflow.net/questions/40485/ffts-over-finite-fields) on MathOverflow for computing the DFT over arbitrary finite fields; you might find the answers relevant.  

---

## 1 answers

### Answer by username_0 on 2011-07-28. Score: 8

A recent [paper](http://eccc.hpi-web.de/report/2010/152/) 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](http://www.cse.psu.edu/~furer/Papers/mult.pdf) in integer multiplication ([reproved](http://arxiv.org/abs/0801.1416) 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](http://cr.yp.to/f2mult/mateer-thesis.pdf) 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.

> **Comments:**
> **username_3**: I think you are right on Furer and De. De does not use complex version of FFT and seems to be easier technically although both algorithms are similar conceptually.  
> **username_4**: If you are worried about log factors you need to be careful about the machine model.  Furer's recent improvement is specifically for Turing machines. For a unit cost RAM model (even without multiplication but with constant time lookup) you get O(n) time for multiplying two n bit numbers and correspondingly lower time complexities for multiplication over F_2 etc. using bit packing and classic techniques.  

---

