Big Number Modular Reduction
Opened this issue · 3 comments
This really should be broken into two issues. Currently we have Barret reduction implemented, and it is ready to go. It also would be nice to have Montgomery reduction but the code for that on github is currently not exactly correct, because we were lacking the ability to find a modular inverse. Well that is a situation I plan on fixing today, so by the end of today we should have both Montgomery and Barret reduction.
By the way, I think Montgomery reduction should be preferred for modular exponentiation because it uses fewer operations and so I am expecting our implementation to be faster that way. But it is impossible to use Montgomery reduction without bringing numbers into Montgomery form, and to get numbers into Montgomery form you need some other kind of reduction. So, the plan is to use Barret reduction in an initial step to get to Montgomery form and then Montgomery reduction thereafter.
Montgomery reduction is available now too.