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