search

Co-dfns / mystika

High-end Cryptographic Library
GNU Affero General Public License v3.0
43 stars 26 forks source link

Big Number Modular Reduction #37

Open arcfide opened 7 years ago

Tikhon03 commented 7 years ago

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.

Tikhon03 commented 7 years ago

Montgomery reduction is available now too.

arcfide commented 7 years ago

This is a good candidate for the public interface provided that we have black box tests to verify that it is working the way that we intend. I’ll leave this open until we can get those tests.

-- Aaron W. Hsu | arcfide@sacrideo.us | http://www.sacrideo.us Support my Open Work: http://www.gratipay.com/Co-dfns/

From: Tikhon03 Sent: Thursday, June 1, 2017 3:54 PM To: arcfide/mystika Cc: Aaron W. Hsu; Author Subject: Re: [arcfide/mystika] Big Number Modular Reduction (#37)

Montgomery reduction is available now too. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.