mpz_powm and mpz_powm_ui, two questions
Torbjörn Granlund
tg at gmplib.org
Fri Mar 11 12:06:48 UTC 2016
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
More information about the gmp-discuss
mailing list