[Solved]: Multiplication in $O(ncdot log n)$

As @DavidRicherby already points out, the confusion arises because different measures of complexity are getting mixed up. But let me elaborate a bit. Usually, when studying algorithms for polynomial multiplication over arbitrary rings, one is interested in the number of arithmetic operations in the ring that an algorithm uses. In particular, given some (commutative, unitary) ring $R$, and two polynomials $f,g in R[X]$ of degree less than $n$, the Schönhage-Strassen algorithm needs $O(n log{n} log{log{n}})$ multiplications and additions in $R$ in order to compute $fg in R[X]$ by, roughly, adjoining $n$-th primitive roots of unity to $R$ to get some larger ring $D supset R$ and then, using the Fast Fourier Transform over $D$, computing the product in $D$. If your ring contains an $n$-th root of unity, then this can be sped up to $O(n log n)$ operations in $R$ by using the Fast Fourier Transform directly over $R$. More specifically, over $mathbb{Z} subset mathbb{C}$, you can do this using $O(n log n)$ ring operations (ignoring the fact that this would require exact arithmetic over the complex numbers). The other measure that can be taken into account is the bit complexity of an operation. And this is what we are interested in when multiplying two integers of bit length $n$. Here, the primitive operations are multiplying and adding two digits (with carry). So, when multiplying two polynomials over $mathbb{Z}$, you actually need to take into account the fact that the numbers that arise during computation cannot be multiplied using a constant number of primitive operations. This and the fact that $mathbb{Z}$ doesn’t have an $n$-th primitive root of unity for $n > 2$ prevents you from appling the $O(n log n)$ algorithm. You overcome this by considering $f,g$ with coefficients from the ring $mathbb{Z}/langle 2^n + 1 rangle$, since the coefficients of the product polynomial will not exceed this bound. There (when $n$ is a power of two), you have (the congruence class of) $2$ as an $n$-th root of unity, and by recursively calling the algorithm for coefficient multiplications, you can achieve a total of $O(n log n log log n)$ primitive (i.e., bit) operations. This then carries over to integer multiplication. For an example that nicely highlights the importance of the difference between ring operations and primitive operations, consider two methods for evaluating polynomials: Horner’s method and Estrin’s method. Horner’s method evaluates a polynomial $f = sum_{i=0}^n f_i X^i$ at some $x in mathbb{Z}$ by exploiting the identity $$f(x) = (ldots (f_n x + f_{n-1})x + ldots + ldots) + f_0$$ while Estrin’s method splits up $f$ into two parts $$H = sum_{i=1}^{n/2} f_{n/2+i} X^i$$ and $$L = sum_{i=0}^{n/2} f_{i} X^i$$ i.e., $H$ contains the terms of degree $>n/2$ and $L$ the terms of degree $leq n/2$ (assume $n$ is a power of two, for simplicity). Then, we can calculate $f(x)$ using $$f(x) = H(x)x^{n/2} + L(x)$$ and applying the algorithm recursively. The former, using $n$ additions and multiplications, is proven to be optimal w.r.t. the number of additions and multiplications (that is, ring operations), the latter needs more (at least $n + log n$). But, on the level of bit operations, one can (quite easily) show that in the worst case, Horner’s method performs $n/2$ multiplications of numbers of size at least $n/2$, leading to $Omega(n^2)$ many bit operations (this holds even if we assume that two $n$-bit numbers can be multiplied in time $O(n)$), whereas Estrin’s scheme uses $O(n log^c n) = tilde{O}(n)$ operations for some $c > 0$, which is, by far, asymptotically faster.