# Schönhage–Strassen algorithm

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).

-
@MartinBerger: For your information in view of your edit-summary, umlauts in titles work in principle, but html-entities are escaped, so one cannot enter them in this way (which from the usage in the body I assume was what you tried). –  quid Jul 19 '13 at 12:19

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.

-
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.