Performance of modular exponentiation

Ivo maffei 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:
>>>> 
>>>> https://gmplib.org/~tege/modexp-silent.pdf
>>>> But this is perhaps the topic of another thread.
>>> 
>>> The GMP manual, 15.4.2, says it is using the sliding window algorithm.
>> 
>> https://gmplib.org/manual/Low_002dlevel-Functions#Low_002dlevel-functions-for-cryptography
> 
> It is not mentioned in the upthread cited algorithms chapter.
> 
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss



More information about the gmp-discuss mailing list