mpz_nextprime

[Torbjörn Granlund]

"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