Performance of modular exponentiation
ivomaffei at gmail.com
Tue Dec 8 11:28:12 UTC 2020
Thanks for the replies, however I think I explained myself badly.
I understand the high-level algorithms used i.e. sliding window, Toom multiplication and Montgomery reduction.
If I understand the source code correctly, the sliding window “core” is in the macro INNERLOOP in mpn_powm.
Mpz_powm contains a lot more code that confuses me a little.
I would like to know if there are _practical_ optimisations that are meant to substantially improve performance.
The chapter 15.8 "Assembly Code” list quite a few such techniques. Is there something done at the C level?
> Il giorno 7 dic 2020, alle ore 22:12, Hans Åberg <haberg-1 at telia.com> ha scritto:
>> On 7 Dec 2020, at 23:06, Marc Glisse <marc.glisse at inria.fr> wrote:
>> On Mon, 7 Dec 2020, Hans Åberg wrote:
>>>> Anyway, here is how to do exponentiation of sensitive data:
>>>> But this is perhaps the topic of another thread.
>>> The GMP manual, 15.4.2, says it is using the sliding window algorithm.
> It is not mentioned in the upthread cited algorithms chapter.
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
More information about the gmp-discuss