mpz_powm and mpz_powm_ui, two questions

[Torbjörn Granlund]

tsurzin <tsurzin at comcast.net> writes:

  It seems that these functions have already been rewritten.  If so can
  I get a pre-release copy?
  
The only code which is ready to share is in the GMP repo.

  If I understand a part of the pseudo code the exponent e is converted
  into e1 + e2 where e1 is the lower 64 bits (word size) and e2 is what
  is left.  Now e2 can be factored into (2^64)*(e2 right shifted 64
  bits).  Since a^(b*c) = (a^b)^c the problem is now converted into a
  base b^e1 step times a (b^(2^64))^(shifted_e2) step. Now shifted_e2
  can be converted and so on.
  
I assume you're referring to the code at https://gmplib.org/devel/.
There is no exponent boundary at bit 64.  Any exponent bondaries are
implicit.

The improvements of t the tweaked algorithm are:
(1) Reduce mod operations when the base is small
(2) Avoid the REDC conversion when the exponent is small.

This will help e.g. Miller-Rabin marginally when using small bases
there.  Since one typicaly tests quite large numbers with Miller-Rabin,
it might be hard to measure the improvement.
  

-- 
Torbjörn
Please encrypt, key id 0xC8601622