The best complexity these days [1]  is essentially n log n. More precisely, O( n log n 8^(log* n) ), where log* is the extremely slow-growing iterated logarithm. The original Schönhage-Strassen algorithm is O(n log n log log n).<p>[1] <a href="http:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1407.3360" rel="nofollow">http:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1407.3360</a>