>In our case, the problem is no longer to calculate Fibonacci numbers – the problem is now to find a way to multiply large integers together efficiently. As far as I can tell, GMP is already state-of-the-art when it comes to that, and tends to come out ahead on most benchmarks.

And actually, the best known method of multiplying large integers is achieved with an FFT over the integers mod 2^n (which is what GMP does). So then your task is changed yet again to optimizing a modular FFT algorithm...