mpz_nextprime
Torbjörn Granlund
tg at gmplib.org
Wed Sep 4 15:35:33 UTC 2019
"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
> I think I've seen comments in the literature saying that 2^e mod m is
> "obviously" more efficient than general modular exponentiation. But as
> far as I can tell, b^e mod m with small b needs essentially one modular
> squaring per bit in the exponent, including the special case b = 2. But
One modular squaring and some products ...
> And I'm not sure how well we currently do small-base modexp in gmp.
We basically do not do anything special. So that small-base or large-base
will take the same time.
With the special case b=2 one may save a few operation seeding the process
with a 2-power smaller than the modulus, but this is a little saving.
Moreover one may avoid the windowing on the exponent (we currently
pre-compute b^3, b^5, b^7... so that we need fewer products) and use a
shift by a single bit every time a multiplication times the base is
needed.
Since we use a REDC-representation, implementing this is not completely
obvious, but anyway it shoul not be too difficult.
This means writing a special function for b=2, not for more general small
bases. Currently I do not have the time to, anyone?
For small bases, avoiding REDC is the way to go. Then, what remains is
essentially the squarings. The multiplications by b will be very cheap.
So yes, a small b is "obviously" cheaper in some typical situation.
Now, one wil pay a small price for not using REDC. That price decreases
with m.
With k-ary modexp, the number of multiplications is log2(n)/k,
while the number of squarings are log(n). Therefore a small b will not
make a huge difference.
As Marco points implies, one may handle some special values like b = 2
also in REDC coding and still not pay the price of a full
multiplication.
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list