FFT i NTT (Nember Theoretical Transform) su definitivno najbrži algoritmi za jako veliki broj cifara. Međutim, neki drugi algoritmi su brži za manji brojem cifara. Preporučujem ti da pročitaš dokumentaciju za GMP. Tamo piše šta on koristi u kojem slučaju, a koristi više algoritama.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.