1
$\begingroup$

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?

$\endgroup$

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.