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.
More information about the gmp-discuss
mailing list