比較してみました。

・比較 Program
　　GMP版 〜 ttp://ideone.com/TYk8gg (ttp://toro.2ch.net/test/read.cgi/tech/1357748713/944)
　　FFT版 〜 ttp://ideone.com/9jNwyP (>>146) 改
・Linux distro 〜 Scientific Linux 6.3　/　Debian 7
・kernel 〜 2.6.32-279.22.1.el6.i686　/　3.2.0-4-686-pae
・glibc 〜 2.12-1.80.el6_3.7(i686)　/　2.13-38
・GMP 〜 4.3.1-7.el6_2.2(i686)　/　2:5.0.5+dfsg-2 (v5.0.5 ?)
・gcc 〜 4.4.6 20120305 (Red Hat 4.4.6-4)　/　4.7.2 (Debian 4.7.2-5)
・計測条件 〜 gcc -O3 でコンパイル / [素数]^[素数]-1の計算 / 2回実行して速い方の値を採用
・計測機器 〜 東芝ダイナブックAX53C
・比較結果
　2^57885161 -1 (17425170 桁)
　　Sci.GMP版 〜 計算　0.000s / 出力 84.08s / 合計 84.080s
　　　　FFT版 〜 計算 32.420s / 出力　2.06s / 合計 34.480s　[勝]
　　Deb.GMP版 〜 計算　0.000s / 出力 29.57s / 合計 29.570s　[勝]
　　　　FFT版 〜 計算 30.870s / 出力　1.06s / 合計 31.930s
　113^8487337 -1 (17425169 桁)
　　Sci.GMP版 〜 計算　3.510s / 出力 84.04s / 合計 87.550s
　　　　FFT版 〜 Segmentation Fault
　　Deb.GMP版 〜 計算　2.200s / 出力 29.66s / 合計 31.860s
　　　　FFT版 〜 Segmentation fault
　113^4243667 -1 (8712582 桁)
　　Sci.GMP版 〜 計算　1.710s / 出力 33.99s / 合計 35.700s
　　　　FFT版 〜 計算 22.800s / 出力　 2.1s / 合計 24.900s　[勝]
　　Deb.GMP版 〜 計算　1.010s / 出力 12.64s / 合計 13.650s　[勝]
　　　　FFT版 〜 計算 21.580s / 出力　0.53s / 合計 22.110s

環境により結果が異なるようです。