4
$\begingroup$

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$
  • $\begingroup$ Just a thought $x^{2n}-1$ has the factors $x^n+1$ and $x^n-1$. $\endgroup$ – mathreadler Sep 15 '15 at 13:02
1
$\begingroup$

I found an answer in Bernsteins Paper. The first part is found in: http://cr.yp.to/lineartime/multapps-20080515.pdf 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.

| cite | improve this answer | |
$\endgroup$
0
$\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].

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.