My math prof said it is trivial to optimize a modular exponentiation (a^b mod c) problem for large values using fft, but I can't figure out how to do this. I looked it up and found a few papers on it (namely [1], [2], and [3]), but 2 of them use Montgomery multiplication, although in different ways, and the third one uses a completely different algorithm to the best of my understanding. I didn't fully understand the papers and can't find anything else on this subject outside these 3 papers. How would one do this?


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.