Performance of modular exponentiation

[Hans Åberg]

> On 7 Dec 2020, at 21:09, Torbjörn Granlund <tg at gmplib.org> wrote:
> 
> Ivo maffei <ivomaffei at gmail.com> writes:
> 
>  I’m a DPhil student at the university of Oxford and I’m looking at
>  parallelising modular exponentiation (mpz_powm).  I’m using the GMP
>  6.2.1 release for C and it is really fast. Could someone explain me
>  how GMP achieves this performance?  If anyone has a somewhat detailed
>  documentation of the code, that would also be very useful as the
>  source code is quite convoluted.
> 
> There is an algorithms chapter in the manual.  The text about modular
> exponentiation is terse, but accurate.

Incidentally, the sliding windows method caused a vulnerability in GnuPG:

https://en.wikipedia.org/wiki/GNU_Privacy_Guard#Vulnerabilities
https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Sliding-window_method