Schönhage–Strassen algorithm

Question

After brief intro to Fourier series, CFT, DFT and their basic properties I enjoyed implementing forward and backward FFT algorithm in complex numbers. I was happy to, at least, have an idea how is it possible that the algorithm works :)

But! My objective is to implement fast integer multiplication algorithm so I began to study The Schönhage–Strassen algorithm (well written here, page 56 of the book/page 72 of the pdf). Also in some other papers I found reference to weighting. And this is what bothers me now.

Why do we need to weight the polynomial coeficients ($a_j$ and $b_j$) with $\theta^j$ before the transformations and unweight the convoluted coeficients ($c_j$) with $K\theta^j$?

There was no weighting function in complex FFT. 'Only' a normalization factor $1/2$ in the backward FFT. I think I've missed some important point :(

I also wonder if the SSA algorithm presendet by Brent & Zimmermann is better/faster/more efficient than algorithm presented here (the approach suggested by Schönhage and Strassen).

Answer 1

I don't have a direct answer for your question, but you might like the book H.J. Nussbaumer: Fast Fourier Transform and Convolution Algorithms. Published 1981, 2nd Edition 1982, Springer-Verlag. It has a lot of material about finite-field FFT's and so-called number-theoretic transforms. It may be out of date by now, but I remember finding it interesting when I was looking into this subject a while back.

Answer 2

You could double check with Modern Computer Algebra, p.238 - I believe the factors $\theta^j$ are evolving by adjoining "virtual" roots of unity, so that we compute a DFT in $R[x]/\langle x^n+1\rangle$ instead in $R[x]/\langle x^n - 1\rangle$. This is also the content of remark 2 in Modern Computer Arithmetic.

SSA isn't really a DFT - for a DFT you would need a principal root of unity. While DFT multiplication is based on cyclic convolution, SSA uses a negative wrapped convolution.

The algorithm 2.4 in Brent & Zimmermann is a SSA.