Trying to understand the Schonhage-Strassen algorithm for multiplying two polynomials $f(X)$, $g(X)$ of degree $n$ over a finite field $\mathbb{F}_q[X]$ with $q$ a prime such that $q-1$ does not have high $2$-adicity (which is necessary for the basic FFT). As I understand, the asymptotic complexity is $O(n\cdot \log(n)\cdot \log(\log(n))).$

But is the multiplicative complexity (i.e. the number of $\mathbb{F}_p$ multiplications) also $O(n\cdot \log(n)\cdot \log(\log(n)))$?

Or is it the case that the additive complexity (i.e. the number of $\mathbb{F}_p$ multiplications)) is $O(n\cdot \log(n)\cdot \log(\log(n)))$ while the multiplicative compexity is $O(n\cdot \log(n))$?

The 1971 Schonhage-Strassen paper is in German. The Cantor-Kaltofen algorithm which generalizes it to polynomial products over an arbitrary ring appears to have an additive complexity of $O(n\cdot \log(n)\cdot \log(\log(n)))$ and a multiplicative complexity of $O(n\cdot \log(n)).$



You must log in to answer this question.