mpz_powm and mpz_powm_ui, two questions

[tsurzin]

mpz_powm and mpz_powm_ui, two questions

It seems that these functions have already been rewritten.  If so can I 
get a pre-release copy?

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.

If we call the nth exponent piece en (for e sub n) can we not reverse 
the order of exponentiation and do (b^en)^((2^64)^(n-1)) instead?  If we 
save a table of the first 64 b^n mod m values from the first step can we 
not reuse them in all steps?  It seems like fewer mod operations would 
be needed since the final power of 2 exponentiation and modular 
reductions would be done by squaring.  If the final reductions become 
too costly we could always form a new table of powers of b for the next 
steps or increase the number of exponent bits per step with an increased 
memory cost.  (Is there a better trick to do a power of 2 exponentiation?)

The Miller-Rabin test makes heavy use of this function so the 
performance of the 64 bit steps allows and limits the size of candidate 
primes that can be tested.  Consider a 100,000,000 digit prime, the 
exponent would have 332192810 bits and so would need 5,190,513 steps for 
a single powm function call.  If each step took 1 second the run time 
would be 60 days.

My desktop has Skylake architecture i7-6700K 4GHz CPU with 32 GB of main 
memory, unfortunately from a GMP standpoint running a 64 bit Windows 10 
Pro OS.  I would like to get a feel for the current step time and am 
considering making other modifications that might make improvements like:
-- using an idle CPU core to do step preparation.
-- maybe further factoring of the 64 bit exponent within the step, for 
example skipping the per bit costs for strings of low bit zeros.
-- adding check point restart output to allow for computer maintenance 
and status checks within a run.

I find the GMP package delightful and am not criticizing the code or its 
algorithms.  Just trying to help.