mpz_powm update

tsurzin tsurzin at
Fri Mar 11 23:22:58 UTC 2016

mpz_powm update

I need to learn more about Montgomery multiplication to have a way to 
estimate whether or not my new reversed order exponentiation algorithm 
has a hope of being faster than the current code. However, the current 
code needs to be faster to let me do what I want.

The new algorithm would seem to save many multiplications and reductions 
and thus could be faster than the current algorithm or possibly combined 
with REDC it might be even faster.

+ I estimate that, overall, it would require about one multiply mod m 
per bit in the exponent.
+ Almost no cost for 0-bits in exponent.
+ Smaller memory footprint.
+ Modest natural improvement for small bases
- per step final exponentiation optimization is complicated.
- Unknown compatibility with Montgomery multiplication

I plan to provide another update when I know more.  Any comments are 
welcome.  A pointer to existing code that does mod m by computing an 
inverse and rounding would be helpful, so I could compute the inverse 
once per function.  I have not found the REDC source code.

More information about the gmp-discuss mailing list