# mpz_powm and mpz_powm_ui, two questions

tsurzin tsurzin at comcast.net
Thu Mar 10 19:33:37 UTC 2016

```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.

```