FFT multiplication

Question

I'm currently implementing a specific polynomial multiplication algorithm for a project. The current goal is to implement chapter 2 of Daniel Bernstein's paper http://cr.yp.to/lineartime/multapps-20080515.pdf. My input will be in the form $\mathbb{R}/(x^{1024}+1)$ which I will convert to $\mathbb{C}/(x^{512}-i)$ after which I will apply the FFT given in the paper, and then convert it back to Real. However I am not sure if I got the right idea. So I made a small example with an 8 degree complex polynomial. It looks like a normal FFT.
My tree would look something like this: $\mathbb{R}/(x^{16}+1)$ => $\mathbb{C}/(x^{8}-i)$ this would split in $\mathbb{C}/(x^{4}+\sqrt i)$ and $\mathbb{C}/(x^{4}-\sqrt i)$ after which those would split again. However, I am not sure how the scaling works afterwards and how I get the right multiplication. Could someone come with a more concrete example how to apply this version of polynomial multiplication?

Answer 1

I figured it out a while ago and just wanted to share the answer. The formulas $\varphi:C/(x^{2n}- c^2) \rightarrow C/(x^{n}- c)$ and $\varphi':C/(x^{2n}- c^2) \rightarrow C/(x^{n}+ c)$ are quite clear. $\mathbb{C}/(x^{8}-i)$ would split into $\mathbb{C}/(x^{4}-\sqrt i)$ and $\mathbb{C}/(x^{4}+\sqrt i)$ according to these formulas. After which $\mathbb{C}/(x^{4}-\sqrt i)$ would split into $\mathbb{C}/(x^{2}-\sqrt{\sqrt i})$ and $\mathbb{C}/(x^{2}+\sqrt{\sqrt i})$. $\mathbb{C}/(x^{4}+\sqrt i)$ would split into $\mathbb{C}/(x^{2}-\sqrt{- \sqrt i})$ and $\mathbb{C}/(x^{2}+\sqrt{- \sqrt i})$. The code below is a c implementation of both the formulas.

void recursive_phi(double complex *x,int n,int lo,double complex root)
{   

  if(n > 1){
    double complex temp;
    int m = n/2;
    for(int i=lo; i < lo+m;++i)
    {
      temp = root * x[i+m];
       //phiprime
      x[i+m] = x[i] - temp;
        //phi
      x[i] = x[i] + temp;
    }
    recursive_phi(x,m,lo,csqrt(root));
    recursive_phi(x,m,lo + m,csqrt(-root));
  }
}

This process is also invertible. Since $\varphi(f) = (f_0 + i f_4) + (f_1 + if_5) x+ (f_2+if_6) x^2+ (f_3+if_7)x^3$ and $\varphi(f) = (f_0 - i f_4) + (f_1 - if_5) x+ (f_2-if_6) x^2+ (f_3-if_7)x^3$. We can now get $f_0$ by adding $(f_0 + if_4)$ with $(f_0 - i f_4)$ which results in $2 f_0$ we can obtain $f_4$ by subtracting instead. Which results in $2f_4*\sqrt i$. I also have some example c code.

void inverse_phi(double complex *x,int n,int lo,double complex root)
{ 
  if(n > 1){
    int m = n/2;
    inverse_phi(x,m,lo,csqrt(root));
    inverse_phi(x,m,lo+m,csqrt(-root));
    double complex temp;
    for(int i=lo;i<m+lo;++i){
      temp = x[i] + x[i+m];
      x[i+m] =  (x[i] - x[i+m]) * conj(root);
      x[i] = temp;
    }
  }
}