I am currently researching Schönhage-Strassen algorithm for class. I am using this article to help me. However, I am stuck on page 13, paragraph 2. I tried a simple example of $x_i = (1,2,3,4,5,6,7,8)$ but I can't figure out how to proceed after performing the Fourier Transform (by hand) as instructed in the article.
Also, I can't figure out why Schönhage-Strassen algorithm has efficiency of $O(n\log(n)\log(\log(n)))$. Can someone provide me with a proof of it?