おそらく最速はGMPでとてもじゃないが敵わないと思う。

http://ideone.com/7swwmd
・41行目はそのままだと大量の出力をするので注意
変更点
・>>911の訂正を反映。
・大きめにメモリを確保していたのをちょうどのサイズで確保するように変更。
計算速度は変わらないはず。
以下参考にしたページ
Wikipedia-高速フーリエ変換
http://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
離散フーリエ変換を用いた多倍長乗算の話
http://homepage2.nifty.com/m_kamada/math/fftmul.htm
FFT (高速フーリエ・コサイン・サイン変換) の概略と設計法
http://www.kurims.kyoto-u.ac.jp/~ooura/fftman/index.html
FFT乗算
http://www.nextftp.com/swlabo/m0_pctech/hp_ultraprecision/up_815_1.htm
FFTアルゴリズムのバリエーション
http://members3.jcom.home.ne.jp/zakii/fourie/31_fft_algorithm.htm
FFT多倍長乗算器のVLSI 設計
http://almond.cs.uec.ac.jp/papers/pdf/2005/syunji-JSIAM9.pdf