I was going through the documentation of GMP (https://gmplib.org/gmp-man-6.1.2.pdf), specially section 15.1.6 where they refer to the use of Fermat's style FFT.

I tried to follow the reference but couldn't quite understand this technique, can anyone explain to me how the Fermat's FFT works?

I don't understand how and why the modulus changes from $(2^N+1)$ to $(2M+k+3)$ using FFT-k splitting?

  • $\begingroup$ The modulus does not change from $2^n + 1$ to $2M + k + 3$; it changes to $2^{2M + k + 3} + 1$. In short, you're splitting your numbers into $2^k$ "digits" of $M$ bits each, and each of these "digits" needs some "slack" for the multiplication to work correctly. Hence you work modulo $2^{2M + k + 3} + 1$ instead of simply $2^M + 1$. This method is explained in §2.3.3 of Modern Computer Arithmetic. $\endgroup$ – Samuel Neves Jun 14 '18 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.