Fast polynomial multiplication and decomposition

(a) Fix integers $q$ and $n$, and let $R = \mathbb{Z}[X] / (q, X^{2^n} + 1)$. (Elements of $R$ are polynomials in $X$, where the coefficients are taken modulo $q$, and $X^{2^n} = -1$.) For a sense of scale, you should imagine that $2^{10} \leq q \leq 2^{64}$, and $2^n \approx 2048$.

We want to perform the following two operations on elements $f$ of $R$.

• Multiplication: Replace $f \leftarrow fg$, for some other polynomial $g$.

• Decomposition: Decompose $f = f_1 B_1 + \cdots + f_d B_d,$ where $B_1, \ldots, B_d$ are fixed polynomials, and $f_1, \ldots, f_d$ are polynomials with small coefficients.

  (For example: You could take $d = n$ and $B_i = 2^{i-1}$, and then let the $f_i$’s be the binary decomposition of $f$.
  But you can choose some other $B_i$’s if it’s reasonable.)

We want to be able to perform a sequence of multiplications and decompositions as quickly as possible. How?

The fastest algorithm we have currently does an FFT at each step; it would be great if we could avoid this.

(b) Now suppose $q = 2^m$ is a power of $2$, so $R = \mathbb{Z}[X] / (2^m, X^{2^n} + 1)$.

Can you come up with a fast algorithm for multiplying elements of $R$?

Here we’re looking for an algorithm that will run fast in practice on real hardware. So:

• It’s easy to add or multiply 64-bit integers modulo $2^{64}$.
• It’s relatively easy to add or multiply floating-point numbers, since chips have built-in support for these operations.