Faster table compute in mpn_sec_powm

Torbjörn Granlund tg at
Tue Mar 20 13:53:16 UTC 2018

In the side-channel silent GMP mpn_sec_powm we compute a table of powers
of the base B, from B^0 to B^k-1 for some table size k.

We do this simple by using the recusrion B^k = B^k*B.
I now realised this can be sped up very easily:

 B^(2j)   = (B^j)^2      (i.e., even values of i)
 B^(2j+1) = (B^(j-1))*B  (i.e., odd values of i)

I.e., for even powers we do a squaring, while for odd numbers we do like

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list