I am using an FFT to multiply polynomials. Because I want the program to be as fast as possible I am leaving away the zero padding. For example, if we want to calculate: $(58 + 37x + 238x^2 + 155x^3)^2$. Apply FFT and then multiply the array with itself and do an inverse FFT. After downscaling the polynomial will be: $71478 + 78072x + 53002x^2 + 35592x^3$. This is a cyclical convolution meaning it is a multiplication modulo $(x^4 - 1)$. However I would like to convert this to a Negacyclic convolution meaning: Multiplication modulo $(x^4 + 1)$. Or universally $(x^n + 1)$. Does anyone have an idea how to accomplish this?
$\endgroup$ 13 Answers
$\begingroup$I found an answer in Bernsteins Paper. The first part is found in: which states the following: One can multiply in $R[x]/(x^{2n} +1)$ with $(34/3)n \log(n) + O(n)$ in R if n is a power of two. Map $R[x]/(x^{2n} +1)$ to $C[x]/(x^n−i)$, twist $C[x]/(x^n−i)$ into $C[x]/(x^n −1)$, and apply the tangent FFT.
Mapping from $R[x]/(x^{2n} +1)$ to $C[x]/(x^n−i)$ is fairly easy. This would look like: $a_0 + a_1 x + \dots + a_{2n-1}x^{2n-1}$ => $(a_0+ i*a_n) + (a_1 + i*a_{n+1})x + \dots + (a_{n-1} + i*a_{2n-1})x^{n-1}$ However twisting to $C[x]/(x^n −1)$ was not clear to me until I found the following in another paper by Bernstein about the Tangent FFT. This could be done by applying $\zeta_{4n}^k$ where $\zeta_n^k= exp^{\frac{k2\pi i}{n}}$. Thus would now be $(a_0+ i*a_n) + (a_1 + i*a_{n+1})\zeta_{4n}^1 x + \dots + (a_{n-1} + i*a_{2n-1})\zeta_{4n}^{n-1} x^{n-1}$. After doing the FFT one needs to inverse this twist and also inverse the mapping.
You can get a fast implementation of negacyclic fft in Palisade crypto library. In this library it has been implemented with Fermat Theoretic Transform and most probably what you are looking for.
$\endgroup$ $\begingroup$One way would be to pad the sequence with zeros to size 2*N, compute the cyclic convolution of this zero-padded sequence in the normal way -- this produces the acyclic convolution of the initial sequence; from which the negacyclic can be easily derived as nega[i] = acyclic[i] - acyclic[N+i].
$\endgroup$ 0
