# 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